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
. . . .
A

Anonymous

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

A

Anonymous

· 2 years ago

class Solution {

  public int moveElements(int[] arr) {
    int slow = 0, fast = 1, n = arr.length;

    while(fast < n && slow < n) {
      if(arr[slow] != arr[fast]) {
        slow++;
        arr[slow] = arr[fast];
      }
      fast++;
    }

    return slow + 1;
  }
}
A

Anonymous

· 2 years ago

class Solution {
  moveElements(arr) {
    let read = 0;
    let lastUnique = 0;
    while (read < arr.length) {
      if (arr[read] !== arr[lastUnique]) { // found new unique value
        const write = Math.min(lastUnique + 1, read);
        arr[write] = arr[read];
        lastUnique = write;
      }
      read += 1;
    }
    return lastUnique + 1; // lengh = lastIndex + 1
  }
}
A

Anonymous

· 2 years ago

It said to not use any additional memory but I needed nonDup , count and next

class Solution {
  moveElements(arr) {
    // TODO: Write your code here
    let nonDup = 1;
    let count = 0;
    for (let next=0; next<arr.length; next++) {
      if (next === 0) continue;
      if (arr[next] !== arr[next-1]) {
        arr[nonDup] = arr[next]
        nonDup++;
        count++
      }
    }
    return count + 1;
  }
}
A

Anonymous

· 3 years ago

class Solution:
	def remove(self, arr):
		writerIndex = 0
		for readerIndex in range(0, len(arr)):
			if arr[readerIndex] != arr[writerIndex]:
				writerIndex += 1
				arr[writerIndex] = arr[readerIndex]
		return writerIndex + 1
A

Anonymous

· 3 years ago

class Solution {

  public int remove(int[] arr) {
    // TODO: Write your code here
    int p=1;
    int q=arr[0];
    for(int i:arr){
      if(q!=i){
        q=i;
        p+=1;
      }
    }
    return p;
  }
}
A

Anonymous

· 3 years ago

class Solution:
  def remove(self, arr):
    # TODO: Write your code here
    hashmap = {}
    for i in arr:
      if i not in hashmap:
        hashmap[i] = 1


    return len(hashmap.keys())
Show 2 replies
A

Anonymous

· 3 years ago

the second example says when the array is not sorted; however, the approach discussed and the code are for sorted arrays.

A

Anonymous

· 3 years ago

class Solution {

  public static int remove(int[] arr) {
    // TODO: Write your code here
    // 思路：数不重复的数 
    // idea: count non-duplicate number
    HashSet<Integer> set=new HashSet<Integer>();
    for(int i:arr){
      set.add(i);
    }
    return set.size();
  }
}
Show 2 replies
A

Anonymous

· 3 years ago

I have another solution just use two pointers pattern and swap 2 elements in that array.

class Solution {

  public static int remove(int[] arr) {
    // TODO: Write your code here
    int n = arr.length;
    int first = 0;
    if (n < 2) return 1;
    int second = 1;
    while (first < n && second < n) {
      if (arr[first] != arr[second]) {
        if (second - first > 1) {
          int tmp = arr[first + 1];
          arr[first + 1] = arr[second];
          arr[second] = tmp;
        }
        first++;
        second++;
      }
      else {
        second++;
      }
    }
    return first + 1;
  }
}

Reading Progress

0%

Vote for new content

On This Page

Problem Statement

Try it yourself