Katkat
Back

Deduplicate an Array in Linear Time

OktaFrontend Engineer · Technical Screen
MediumFrontend EngineerTechnical ScreenCoding & Algorithms

Last updated

This question tests the ability to implement a deduplication algorithm that preserves the original relative order of elements while maintaining O(n) time and space complexity.

Problem Statement

Given an array of primitive values (integers or strings), return a new array containing only the unique elements from the original array. The relative order of the elements in the output must be the same as their first occurrence in the input. You are not allowed to mutate the original input array.

Requirements

  • Time Complexity: O(n), where n is the length of the input array.
  • Space Complexity: O(n) for the auxiliary data structure used to track seen elements.

Function Signature

def deduplicate(arr: list) -> list:
    # Implementation here

Examples

Example 1 Input: [1, 2, 2, 3, 4, 1, 5] Output: [1, 2, 3, 4, 5] Explanation: The second 1 and second 2 are removed because they appeared earlier in the input.

Example 2 Input: ['apple', 'orange', 'apple', 'banana', 'orange'] Output: ['apple', 'orange', 'banana']

Constraints

  • The input array can contain both integers and strings.
  • The input array length can be up to 1,000,000 elements.
  • Values are primitives only.

Hints

Hint 1

Consider using an auxiliary data structure to keep track of elements you have already encountered as you iterate through the array.

Hint 2

A hash-based structure provides constant time lookups on average, which is necessary to meet the linear time complexity requirement.

Hint 3

Ensure the result array only stores an element the first time it is processed by checking against your tracker.

Follow-up questions

  • How would your approach change if you were asked to perform the deduplication in-place (i.e., modifying the input array and using O(1) extra space)?
  • What are the implications for time complexity if the input values are objects or arrays rather than primitives?
  • How would you handle the requirement if you were asked to keep the *last* occurrence of each element instead of the first?