Katkat
Back

Remove Duplicate Integers While Preserving Order

UpstartSoftware Engineer · Online Assessment
EasySoftware EngineerOnline AssessmentCoding & Algorithms

Last updated

This problem tests your ability to filter elements from an array while maintaining the original sequence and ensuring optimal time complexity using auxiliary data structures.

Problem Statement

Given an array of integers nums, return a new array that contains only the first occurrence of each integer from the original array, maintaining their relative order.

Function Signature

def remove_duplicates(nums: list[int]) -> list[int]:

Constraints

  • 1 <= len(nums) <= 1,000,000
  • -10^9 <= nums[i] <= 10^9
  • Time Complexity: O(n) where n is the number of elements.
  • Space Complexity: O(u) where u is the number of unique elements.

Examples

Example 1: Input: nums = [4, 5, 4, 1, 2, 5] Output: [4, 5, 1, 2] Explanation: The second '4' and second '5' are duplicates and are removed.

Example 2: Input: nums = [1, 1, 1, 1] Output: [1]

Edge Cases

  • Empty input array: Return an empty list.
  • Array with all unique elements: Return the original array.
  • Array with all identical elements: Return a list containing one instance of that element.

Hints

Hint 1

To achieve linear time complexity, avoid nested loops or using the 'in' operator on a list.

Hint 2

Use a hash set to keep track of the integers you have already encountered as you iterate through the input list.

Hint 3

Only append an integer to your result list if it is not already present in your hash set.

Follow-up questions

  • How would you solve this if you were forbidden from using additional space (i.e., modifying the array in-place)?
  • What would change if the input array was sorted, and how would that affect your time and space complexity?
  • If the input were a stream of numbers rather than a fixed array, how would your design change to handle incoming data continuously?