Grokking the Coding Interview: Patterns for Coding Questions
Vote

0% completed

​

Find Non-Duplicate Number Instances (easy)

Problem Statement

Try it yourself

Problem Statement

Given an array of sorted numbers, move all non-duplicate number instances at the beginning of the array in-place. The non-duplicate numbers should be sorted and you should not use any extra space so that the solution has constant space complexity i.e., O(1).

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.

Example 1:

Input: [2, 3, 3, 3, 6, 9, 9]
Output: 4
Explanation: The first four elements after moving element will be [2, 3, 6, 9].

Example 2:

Input: [2, 2, 2, 11]
Output: 2
Explanation: The first two elements after moving elements will be [2, 11].

Constraints:

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

Try it yourself

Try solving this question here:

Python3
Python3
. . . .
J

Joseph

· 4 years ago

Problem statement was a little confusing in my opinion, as the solution does not technically remove all duplicates from the array. But at the end, I suppose you could return the subarray of length nextNonDuplicate ? Image

M

monir.imamverdi

· a year 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.

Hussain Zaidi

Hussain Zaidi

· 3 years ago

The problem says: "The relative order of the elements should be kept the same" But in the solution relative order is kept only for the non-duplicate part of the array. Which isn't what the problem suggests.

L

Luis Philipe

· 4 years ago

I believe that the "Similar Questions" requirement is quite simple, to return the new array length we just need to iterate the array and count the non "key" values. Apply two pointers on it is unnecessary.

J

John O'Neill

· 3 years ago

The problem as evaluated by the code runner doesn't actually require removing duplicates — it just requires counting non-duplicates, which isn't really a two pointers problem. To keep myself honest, I actually removed the duplicates, as below.

class Solution:
  def remove(self, arr):
    if not arr:
      return 0
    next_non_duplicate = 1
    for i, num in enumerate(arr):
      if arr[next_non_duplicate - 1] != num:
        arr[next_non_duplicate] = num
        next_non_duplicate += 1
    n = len(arr)
    for _ in range(next_non_duplicate, n):
      arr.pop()
    return len(arr)
M

Mohamed Elsayed

· 4 years ago

The graphical explanation is showing that nextNoneDuplicate starts from 0 while it actually starts from 1

Show 1 reply
C

Casey Dietz

· 3 years ago

I dont understand how the elements are being removed in the solution? I just see two pointers moving through the array checking conditionals but I dont see where they are getting removed. What am I missing?

Show 1 reply
B

Brian Dy

· 4 years ago

The Similar Questions solution is missing the part where it returns a new array or subarray without the duplicates. If the current solution is acceptable, then Two Pointers is unnecessary and we could have just incremented the counter for any element != key.

Show 1 reply
Y

Yvonne

· 4 years ago

There seems to be a typo in the example visual: we start with [2, 3, 3, 3, 6, 9, 9] but end with [2, 3, 6, 6, 9, 9, 9]

Show 1 reply
T

Tomer

· 4 years ago

If the input array is empty, then the proposed solution returns 1, which is incorrect.

Show 1 reply

On This Page

Problem Statement

Try it yourself