Remove duplicates from a list

Summary

Return a new list with duplicates removed while preserving the original order.

Problem statement

Given a list arr, implement remove_duplicates(arr) which returns a new list containing the elements of arr with duplicates removed. The relative order of the first occurrences must be preserved. Use a set to track seen elements to achieve O(n) average time. The function should handle empty input and different repetition patterns.

Task

Implement remove_duplicates(arr) to eliminate repeated values but keep the first occurrence order using a set to track seen values.

Examples

Input format

A list of hashable elements (e.g., integers): [1, 2, 2, 3, 1]

Output format

A list with duplicates removed, preserving the first occurrence order.

Constraints

0 <= len(arr) <= 10^5. Elements are hashable. Aim for O(n) average time and O(n) extra space.

Samples