Dedupe Unsorted Array (Three Variants)

Problem Overview

You are given a method that takes in an array of unsorted integers and you must return the deduped array. The interviewer runs it as three progressively tighter variants, using each one to gauge your understanding of time and space complexity.

Problem Statement

Implement a function dedupe_array that takes an array of integers as input and returns a new array with duplicates removed. The function will be tested with three different constraints:

1. Variant 1: No constraints on time or space complexity.
2. Variant 2: Must use O(n) time complexity.
3. Variant 3: Must use O(n) time complexity and O(1) space complexity.

Examples

Variant 1

Input: [3, 1, 2, 3, 4, 2, 5] Output: [3, 1, 2, 4, 5]

Variant 2

Input: [3, 1, 2, 3, 4, 2, 5] Output: [3, 1, 2, 4, 5]

Variant 3

Input: [3, 1, 2, 3, 4, 2, 5] Output: [3, 1, 2, 4, 5]

Constraints

1. Variant 1: No constraints on time or space complexity.
2. Variant 2: Must use O(n) time complexity.
3. Variant 3: Must use O(n) time complexity and O(1) space complexity.

Hints

• For Variant 1, consider using a data structure like a set to keep track of seen elements.
• For Variant 2, consider using a set or a hash table to store seen elements while iterating through the array.
• For Variant 3, consider using the array itself to store the deduped elements, avoiding the use of additional data structures.

Solution

Variant 1: Using a Set

python def dedupe_array(arr): seen = set() result = [] for num in arr: if num not in seen: seen.add(num) result.append(num) return result

Variant 2: Using a Set with O(n) Time Complexity

python def dedupe_array(arr): seen = set() result = [] for num in arr: if num not in seen: seen.add(num) result.append(num) return result

Variant 3: Using the Array Itself with O(n) Time Complexity and O(1) Space Complexity

`python def dedupe_array(arr): if not arr: return arr

write_index = 1
for read_index in range(1, len(arr)):
    if arr[read_index] != arr[read_index - 1]:
        arr[write_index] = arr[read_index]
        write_index += 1
return arr[:write_index]

`

Web Search Results

• GitHub: No exact matches found.
• 1point3acres: No exact matches found.
• PracHub: No exact matches found.
• Glassdoor: No exact matches found.
• Blind: No exact matches found.
• Reddit (r/cscareerquestions, r/leetcode, r/csMajors): No exact matches found.

The above solution and problem statement are based on the provided excerpt and common interview question patterns.