Home > Reflections | ⏮️ ⏭️

2024-07-02

🏋️ Coding Practice

26. Remove Duplicates from Sorted Array

Given an integer array nums sorted in non-decreasing order, remove the duplicates in-place such that each unique element appears only once. The relative order of the elements should be kept the same. Then return the number of unique elements in nums.
Consider the number of unique elements of nums to be k, to get accepted, you need to do the following things:

• Change the array nums such that the first k elements of nums contain the unique elements in the order they were present in nums initially. The remaining elements of nums are not important as well as the size of nums.
• Return k.

🪞 Reflections

1. < 14 minutes is good
2. no bugs is pretty good
3. the test case may have been a bit longer than necessary, but it got the coverage we needed and we finished in time
4. testing gave confidence in the correct code
5. I remember planning this problem in the past without coding the solution
   1. I didn’t reference my old planning notes, but I did remember the approach
   2. Planning took about the same amount of time this time as it did last time

⌨️ My Solution

/* Remove duplicates from sorted array, sliding k unique elements to the front, return k  
Plan  
1. Use 2 pointers: 1 for reading and 1 for writing  
2. Scan from left to right, advancing the reading cursor to skip duplicates but advancing the writing cursor to write them  
3. track length with a uniques counter  
runtime complexity: O(N)  
extra space complexity: O(1)  
[03:41] done planning  
[08:12] done with initial implementation  
[13:17] done with test (no bugs found)  
[13:48] success on first submission  
*/  
function removeDuplicates(nums: number[]): number { // [1,1,2,2,2,3]  
  let uniqueCount: number = 0  
  for (let r = 0, w = 0; r < nums.length; r++) {  
    const currentValue: number = nums[r] // 3; 2; 2; 2; 1; 1  
    const unique: boolean = r === 0 || nums[r - 1] !== currentValue // T; F; F; T; F; T  
    if (unique) {  
      uniqueCount++ // 3; 2; 1  
      nums[w] = currentValue // [1,2,3,2,2,3]; [1,2,2,2,2,3]; [1,1,2,2,2,3]  
      w++ // 3; 2; 1  
    }  
  }  
  return uniqueCount // 3  
};