Grokking the Coding Interview: Patterns for Coding Questions
Vote

0% completed

​

Solution: Find Non-Duplicate Number Instances

Problem Statement

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

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 starting from the second element (index 1) to the end of the array.
  • 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

Let's walk through the algorithm with the array [2, 3, 3, 3, 6, 9, 9]:

  1. Initialization: Set nextNonDuplicate to 1.

    • Initial Array: [2, 3, 3, 3, 6, 9, 9]
    • nextNonDuplicate = 1

  2. Iteration:

    • i = 1:
      • Compare arr[0] (2) with arr[1] (3)
      • They are different, so copy arr[1] to arr[1] (no actual change)
      • Increment nextNonDuplicate to 2
      • Array: [2, 3, 3, 3, 6, 9, 9]
    • i = 2:
      • Compare arr[1] (3) with arr[2] (3)
      • They are the same, do nothing
      • nextNonDuplicate remains 2
    • i = 3:
      • Compare arr[1] (3) with arr[3] (3)
      • They are the same, do nothing
      • nextNonDuplicate remains 2
    • i = 4:
      • Compare arr[1] (3) with arr[4] (6)
      • They are different, so copy arr[4] to arr[2]
      • Increment nextNonDuplicate to 3
      • Array: [2, 3, 6, 3, 6, 9, 9]
    • i = 5:
      • Compare arr[2] (6) with arr[5] (9)
      • They are different, so copy arr[5] to arr[3]
      • Increment nextNonDuplicate to 4
      • Array: [2, 3, 6, 9, 6, 9, 9]
    • i = 6:
      • Compare arr[3] (9) with arr[6] (9)
      • They are the same, do nothing
      • nextNonDuplicate remains 4

  3. Result: The number of unique elements is nextNonDuplicate, which is 4. The modified array is [2, 3, 6, 9, 6, 9, 9], and the first four elements [2, 3, 6, 9] are the unique elements.

Here is the visual representation of this algorithm for Example-1:

Image

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

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

Solution

Step-by-Step Algorithm

Algorithm Walkthrough

Code

Complexity Analysis

Time Complexity

Space Complexity

Similar Questions

Solution:

Complexity Analysis

Time Complexity

Space Complexity