Grokking the Coding Interview: Patterns for Coding Questions
Vote

0% completed

​

Solution: Find Non-Duplicate Number Instances

Problem Statement

Why this is a Two Pointers problem

Solution

Step-by-Step Algorithm

Algorithm Walkthrough

Code

Complexity Analysis

Time Complexity

Space Complexity

Similar Questions

Solution:

Complexity Analysis

Time Complexity

Space Complexity

Problem Statement

Given an array of numbers sorted in non-decreasing order, remove the duplicates in place so that each distinct value appears only once, keeping the values in sorted order at the front of the array. You may not use any extra space, so the solution must use constant extra space, O(1).

Return k, the number of distinct values. What the array holds beyond the first k positions does not matter and is not checked.

Example 1:

Input: [2, 3, 3, 3, 6, 9, 9]
Output: 4
Explanation: There are four distinct values, so the first four elements become [2, 3, 6, 9]. Whatever sits beyond position 4 is ignored.

Example 2:

Input: [2, 2, 2, 11]
Output: 2
Explanation: There are two distinct values, so the first two elements become [2, 11]. Whatever sits beyond position 2 is ignored.

Constraints:

  • 1 <= nums.length <= 3 * 10<sup>4</sup>
  • -100 <= nums[i] <= 100
  • nums is sorted in non-decreasing order.

Why this is a Two Pointers problem

What the question saysThe signal it matches
"an array of numbers sorted in non-decreasing order", repeated in the constraintsthe input is sorted
"in place", and "not use any extra space, so the solution must use constant extra space"the question says in place or constant extra space
"remove the duplicates ... so that each distinct value appears only once"a duplicate rule, one of the conditions this pattern handles

Nothing is being searched for from both ends, so this is not the converging shape. One pointer reads ahead while the other writes behind it, which is the same direction variant.

The closest alternative. A hash set is the usual way to remove duplicates. That is the Hash Maps pattern. Two facts rule it out here.

The array is sorted, so duplicates are already next to each other. Nothing has to be remembered. Extra space is also forbidden, and a set needs it.

Solution

In this problem, we need to separate the duplicate elements in-place such that the resultant length of the array remains sorted. As the input array is sorted, one way to do this is to shift the elements left whenever we encounter duplicates. In other words, we will keep one pointer for iterating the array and one pointer for placing the next non-duplicate number. So our algorithm will be to iterate the array and whenever we see a non-duplicate number we move it next to the last non-duplicate number we've seen.

Step-by-Step Algorithm

  • Initialize the Index: Start by initializing a variable nextNonDuplicate to 1. This variable will keep track of the position where the next unique element should be placed.
  • Iterate Through the Array: Loop through the array to the end. The code starts the reading index at 0, which costs one comparison of the first element against itself and keeps the loop body uniform.
  • Compare Elements: For each element, check if it is different from the element at the position nextNonDuplicate - 1.
    • If Different: If the current element is different from the element at nextNonDuplicate - 1, copy the current element to the position nextNonDuplicate.
    • Increment Index: Increase the nextNonDuplicate index by 1 to point to the next position for a unique element.
  • Return Result: After completing the iteration, return the value of nextNonDuplicate, which represents the number of unique elements in the array.

Algorithm Walkthrough

mediaLink

The array [2, 3, 3, 3, 6, 9, 9] is sorted, so equal values sit next to each other. One pointer reads ahead and the other marks where the next distinct value should be written. The first value is always distinct, so the writer starts at index 1.

1 of 8

Code

Here is what our algorithm will look like:

Python3
Python3
. . . .

Complexity Analysis

Time Complexity

  • Loop through the array: The algorithm uses a single for loop to iterate through the array. Each element is processed once, so the time complexity of the loop is O(N), where N is the number of elements in the array.
  • Comparison and assignment: Inside the loop, the comparison arr[nextNonDuplicate - 1] != arr[i] and the assignment arr[nextNonDuplicate] = arr[i] are both constant time operations, O(1).

Overall time complexity: O(N).

Space Complexity

  • In-place modification: The algorithm modifies the input array in place and only uses a few extra variables (nextNonDuplicate and i), which require constant space.
  • Since no additional data structures are used that scale with the input size, the space complexity is O(1).

Overall space complexity: O(1).

Similar Questions

Problem 1: Given an unsorted array of numbers and a target key, remove all instances of key in-place and return the new length of the array.

Example 1:

Input: [3, 2, 3, 6, 3, 10, 9, 3], Key=3
Output: 4
Explanation: The first four elements after removing every 'Key' will be [2, 6, 10, 9].

Example 2:

Input: [2, 11, 2, 2, 1], Key=2
Output: 2
Explanation: The first two elements after removing every 'Key' will be [11, 1].

Solution:

This problem is quite similar to our parent problem. We can follow a two-pointer approach and shift numbers left upon encountering the key. Here is what the code will look like:

Python3
Python3
. . . .

Complexity Analysis

Time Complexity

  • Loop through the array: The algorithm uses a single for loop to iterate through the array. Each element is processed exactly once, resulting in a time complexity of O(N), where N is the number of elements in the array.
  • Comparison and assignment: Inside the loop, the comparison arr[i] != key and the assignment arr[nextElement] = arr[i] are both constant-time operations, O(1).

Overall time complexity: O(N).

Space Complexity

  • In-place modification: The algorithm modifies the input array in place and only uses a few extra variables (nextElement and i), which require constant space.
  • Since no additional data structures are used, the space complexity is O(1).

Overall space complexity: O(1).

Gaurav Thapliyal

Gaurav Thapliyal

· 3 months ago

The problem is a bit confusing. To be honest we do not even need to swap the elements as ultimately we are returning the length of array with unique elements. Can be done by tracking with a length pointer

Show 1 reply
Gaurav Thakur

Gaurav Thakur

· 5 months ago

To Justify the statement "Move all the unique number instances at the beginning of the array and after moving return the length of the subarray that has no duplicate in it.", It has to move the elements, not just count.

Another problem is with the test cases. If input is empty array, it is expecting 1 as output. Logically, in that case it should be 0.

class Solution {

public int moveElements(int[] arr) {

if(arr.length < 2) {

return arr.length;

}

int index = 1;

int ndi = 0;

while(index < arr.length) {

if(arr[index] == arr[ndi]) {

index++;

} else {

if(index != ndi+1) {

swap(arr, index, ndi+1);

}

index++;

ndi++;

}

}

return ndi + 1;

}

private void swap(int[] arr, int i, int j) {

int temp = arr[i];

arr[i] = arr[j];

arr[j] = temp;

}

}

Show 1 reply
beruss sama

beruss sama

· 5 months ago

class Solution:

  def moveElements(self, arr):

    ans = 0

    for i in range(1, len(arr)):

      if arr[i] != arr[i-1]:

        ans += 1

    return 1 + ans
Show 1 reply
David Bishop

David Bishop

· 6 months ago

I wasted so much time on this question even though i had the solution almost immediately because it said you had to actually move the items in the array, so i figured it was required. Should have known since the array is never returned its functionally the same to just count the non duplicates.

Show 1 reply
wasim ahmed

wasim ahmed

· 6 months ago

class Solution:
  def moveElements(self, arr):
    # TODO: Write your code here
    n = len(arr)
    for curr in range(n):
      nxt = curr + 1
      while nxt < n and arr[curr] >= arr[nxt]:
        nxt += 1
      if nxt == n:
        break
      if nxt < n and arr[curr] < arr[nxt]:
        arr[curr+1], arr[nxt] = arr[nxt], arr[curr + 1]
    return curr + 1
Show 1 reply
A

anjoiype

· a year ago

The problem says return the number of non duplicates. For e.g. [1,1,2,3,3,4,5,5,5]. Here the non duplicate numbers are 2 and 4. Rest all are duplicated. So the answer should be 2 instead of 5

Show 1 reply
Rahil Dhodapkar

Rahil Dhodapkar

· 2 years ago

class Solution:

def moveElements(self, arr):

write_idx = 1

curr_val = arr[0]



for read_idx in range(1, len(arr)):

  if arr[read_idx] > curr_val:

    curr_val = arr[read_idx]

    arr[write_idx], arr[read_idx] = arr[read_idx], arr[write_idx]

    write_idx += 1



return write_idx
Show 1 reply
M

monir.imamverdi

· 2 years ago

This page needs to be rewritten, it's so confusing.

We're expecting the first occurrence of each distinct number to be retained in the final output, rather than only keeping numbers that appear exactly once. That means instead of filtering strictly unique elements, we need to retain distinct elements in their first occurrence while shifting them to the front.

Razvan

Razvan

· 2 years ago

class Solution {
  moveElements(arr) {
    return [...new Set(arr)].length;
  }
}
Show 1 reply
Nabeel Keblawi

Nabeel Keblawi

· 2 years ago

I know we're using 2 pointers and that was my initial solution, but the challenge was it kept swapping even after all non-duplicate values were found. So I found an easier shortcut with one line of code:

return len(set(arr))

And it passed all test cases. But if we insist on using two pointers to solve this one, I'd go with the provided solution.

Show 2 replies

Reading Progress

0%

Vote for new content

On This Page

Problem Statement

Why this is a Two Pointers problem

Solution

Step-by-Step Algorithm

Algorithm Walkthrough

Code

Complexity Analysis

Time Complexity

Space Complexity

Similar Questions

Solution:

Complexity Analysis

Time Complexity

Space Complexity