High Level

We are using anchor/runner pointer strategy to solve this problem. At a high level, our approach is to use anchor to keep track of our distinct elements at the beginning of the array, while runner looks for the next distinct element. We'll increment runner on each iteration, comparing elements to anchor as we go. When anchor and runner are different we have found the next distinct element and we can update our array. When anchor and runner are the same, we've found a duplicate and we can ignore it, continuing on.

Note that this algorithm depends on the array being sorted. Duplicates in a sorted array are always adjacent, and we'll capitalize on that fact here. Now let's look at a more detailed algorithm.

Algorithm

• Initialize anchor to 0, the index of the first element of the array. anchor represents the position of the last distinct element that we've either confirmed or written. We know that the first element of our array is distinct, so we can start with anchor at 0.

• Initialize runner to 1. runner will be used to scan through the array. We already know that the element at 0 is distinct, so we can start searching for other distinct elements at 1.

• Start looping. During each iteration, compare the element at the runner position, nums[runner], with the element at the anchor position, nums[anchor]:

  • If nums[runner] differs from nums[anchor], it indicates that nums[runner] has reached the next distinct element. This is because, in a sorted array, all duplicates are adjacent.
    • Increment the anchor to advance to the subsequent position. This is where we'll place our new distinct element.
    • Assign the value of nums[runner] to nums[anchor]. This action effectively moves the unique element to the front portion of the array.
    • Increment runner by 1. Since we've checked this element, we can move to the next.
  • If nums[runner] is equal to nums[anchor], it means nums[runner] is a duplicate, and we can ignore it.
    • Increment runner and continue on.

• Keep looping until runner has scanned through the entire array.

• Since anchor represents the index of the last unique element in the modified array, the total number of unique elements is anchor + 1, which we can return.

Time Complexity

The time complexity of the compressToDistinct function is O(N), where N is the length of the input array nums. This is because the function uses a single loop that iterates through the array exactly once. In each iteration, the function performs constant-time operations, such as comparison and assignment.

Space Complexity

The space complexity of this algorithm is O(1). The function modifies the input array in-place without utilizing any additional data structures that grow with the size of the input.

Walkthrough

Let's go through the example array [3, 3, 5, 7, 7, 8] step by step.

Step 1: In the first step we initialize two pointers anchor (a) at index 0, and runner (r) at index 1.

Step 2: We are compare the elements at the anchor and runner positions. Since they are the same, we increment the runner by 1.

Step 3: Once again, we compare the elements at the anchor and runner positions.

Step 3.1: Since the elements are different, we first increment the anchor pointer by 1.

Step 3.2: Then, we write the element at the runner position to the new anchor position, and increment the runner pointer by 1.

Step 4: In the fourth iteration, the elements at the anchor and runner positions are different yet again.

Step 4.1: We first increment the anchor pointer by 1.

Step 4.2: Then, we write the element at the runner position to the new anchor position, and move the runner pointer by 1.

Step 5: In this iteration, the elements at the anchor and runner positions are the same, so we increment the runner by 1.

Step 6: In the final iteration, the elements at the anchor and runner positions are different.

Step 6.1: We first increment the anchor pointer by 1.

Step 6.2: Then, we write the element at the runner position to the new anchor position, and increment the runner pointer by 1.

runner has made it through the array and we can stop iterating. Since the anchor represents the index of the last unique element in the modified array, the total number of unique elements is anchor + 1, so we return 4.

Solution Code

function compressToDistinct(nums) {
  if (nums.length <= 1) return nums.length;

  let anchor = 0;

  for (let runner = 1; runner < nums.length; runner++) {
    if (nums[runner] !== nums[anchor]) {
      anchor++;
      nums[anchor] = nums[runner];
    }
  }

  return anchor + 1;
}