Remove Duplicates From Sorted Array Solution for Accenture

Company: Accenture · Difficulty: Easy · Topics: Array, Two Pointers

Problem Statement

Given an integer array nums sorted in non-decreasing order, remove the duplicates in-place such that each unique element appears only once.

Key Understanding:

• The array is already sorted in non-decreasing order
• We need to remove duplicates in-place (modify the original array)
• We should return the new length of the array after removing duplicates
• The first k elements should contain the unique elements in sorted order
• The remaining elements can be ignored (they don't affect the result)

Examples

Example 1:

Input: nums = [1,1,2]

Output: 2, nums = [1,2,_]

Explanation:

• Original array: [1,1,2]
• After removing duplicates: [1,2,_] (where _ represents ignored elements)
• Return length: 2
• First 2 elements: [1,2] (unique elements in sorted order)

Example 2:

Input: nums = [0,0,1,1,1,2,2,3,3,4]

Output: 5, nums = [0,1,2,3,4,_,_,_,_,_]

Explanation:

• Original array: [0,0,1,1,1,2,2,3,3,4]
• After removing duplicates: [0,1,2,3,4,_,_,_,_,_]
• Return length: 5
• First 5 elements: [0,1,2,3,4] (unique elements in sorted order)

Example 3:

Input: nums = [1,2,3,4,5]

Output: 5, nums = [1,2,3,4,5]

Explanation:

• Original array: [1,2,3,4,5] (no duplicates)
• After removing duplicates: [1,2,3,4,5] (no change)
• Return length: 5
• All elements are unique

Example 4:

Input: nums = [1,1,1,1,1]

Output: 1, nums = [1,_,_,_,_]

Explanation:

• Original array: [1,1,1,1,1] (all duplicates)
• After removing duplicates: [1,_,_,_,_]
• Return length: 1
• Only one unique element: [1]

Intuition

The key insight is that since the array is sorted, all duplicates will be adjacent. We can use two pointers to keep track of where to write the next unique element.

Core Concept:

• Since the array is sorted, duplicates appear consecutively
• We can use a "write" pointer to track where to place the next unique element
• We can use a "read" pointer to scan through the array
• When we find a new unique element, we write it at the write pointer position

Why Two Pointers Work:

• The first element is always unique (no previous element to compare with)
• For subsequent elements, we compare with the previous element
• If they're different, it's a new unique element
• If they're the same, it's a duplicate that we skip

Approach

Approach 1: Two Pointers (Optimal)

Algorithm:

1. Handle edge case: if array is empty, return 0

2. Initialize write pointer at index 1 (first element is always unique)

3. Iterate through array starting from index 1 (read pointer)

4. For each element:

• If current element is different from previous element:
• Write current element at write pointer position
• Increment write pointer
• If current element is same as previous element:
• Skip (do nothing)

5. Return write pointer (length of unique elements)

Why This Works:

• The first element is always unique and stays in place
• We only write elements when we encounter a new unique value
• Since array is sorted, duplicates are adjacent
• Write pointer always points to the next position to write a unique element

Complexity Analysis:

• Time: O(n) - Single pass through the array
• Space: O(1) - Only constant variables needed

Approach 2: Using Extra Array

Algorithm:

1. Create a temporary array to store unique elements

2. Copy the first element to temp array

3. Iterate through original array starting from index 1

4. If current element is different from previous element:

• Add to temp array

5. Copy temp array back to original array

6. Return length of temp array

Why This Works:

• We preserve the original array and build a new one
• Simple and straightforward approach
• Guaranteed to work correctly

Complexity Analysis:

• Time: O(n) - We traverse the array twice
• Space: O(n) - We need extra array

Approach 3: Count and Shift

Algorithm:

1. Initialize unique count to 1 (first element is always unique)

2. Iterate through array starting from index 1

3. If current element is different from previous element:

• Shift elements to fill gaps
• Increment unique count

4. Return unique count

Why This Works:

• We maintain the array structure by shifting elements
• More complex but doesn't require extra space
• Less efficient due to shifting operations

Complexity Analysis:

• Time: O(n²) - Shifting operations can be expensive
• Space: O(1) - No extra space needed

Dry Run

Let's trace through Example 1: nums = [1,1,2]

Two Pointers Approach:

Initial State: write = 1, nums = [1,1,2]

Step 1: read = 1, write = 1

• nums[1] = 1, nums[0] = 1
• Current element (1) == Previous element (1) ✓
• Skip (do nothing)
• nums = [1,1,2], write = 1

Step 2: read = 2, write = 1

• nums[2] = 2, nums[1] = 1
• Current element (2) != Previous element (1) ✓
• Write nums[2] at nums[write] = nums[1]
• nums = [1,2,2], write = 2

Step 3: read = 3 (end of array)

• Stop the loop
• Return write = 2

Final Result: Length = 2, nums = [1,2,2] (first 2 elements are unique)

Extra Array Approach:

Step 1: Create temp array

• temp = []

Step 2: Copy first element

• temp = [1]

Step 3: Process remaining elements

• nums[1] = 1, previous = 1: Same, skip
• nums[2] = 2, previous = 1: Different, add to temp
• temp = [1,2]

Step 4: Copy back to original

• nums = [1,2,2]

Final Result: Length = 2, nums = [1,2,2]

Key Insights

1. Sorted Array Property: Since array is sorted, duplicates are adjacent

2. First Element: Always unique and stays in place

3. Two Pointers: Write pointer tracks where to place next unique element

4. In-Place Modification: We can modify the array without extra space

5. Return Length: The function should return the new length, not the modified array

Edge Cases

1. Empty Array: Return 0

2. Single Element: Return 1 (always unique)

3. All Duplicates: Return 1 (only one unique element)

4. No Duplicates: Return original length (no changes needed)

5. Large Arrays: Handle efficiently with two pointers

Solution

⚠️ Disclaimer: Don't jump directly to the solution, try it out yourself first. Only look at the solution after you've given it a good attempt.

Solution 1: Two Pointers (Optimal)

Time Complexity: O(n) - We traverse the array once

Space Complexity: O(1) - We use only constant extra space

Advantages:

• Most efficient approach
• Constant space usage
• In-place modification
• Single pass through array

Disadvantages:

• Modifies the original array
• Requires understanding of two pointer technique

Solution 2: Using Extra Array

Time Complexity: O(n) - We traverse the array twice

Space Complexity: O(n) - We need extra array

Advantages:

• Preserves original array
• Simple and straightforward
• Easy to understand and implement

Disadvantages:

• Uses extra space
• Requires two passes through array
• Less efficient than in-place approach

Solution 3: Count and Shift

Time Complexity: O(n²) - We may need to shift elements

Space Complexity: O(1) - We use only constant extra space

Advantages:

• Constant space usage
• In-place modification

Disadvantages:

• Highly inefficient due to shifting
• Quadratic time complexity
• Complex implementation
• Not suitable for large arrays

More Accenture coding questions