Open Bookshelf Cover Page
Preface
Getting Started
- Prerequisites
- Introduction
The PEDAC Approach to Problem Solving
Introduction to Data Structures and Algorithms
Sorting Algorithms
Pointer-Based Mental Models
Binary Search
Linked Lists
Stacks & Queues
Conclusion
- Conclusion & Next Steps
Share on

Practice: Compress to Distinct Elements

In this assignment, we'll practice the techniques learned so far using the "Compress to Distinct" problem. Try to solve the problem using the naive (brute-force) approach first, and then see if you can optimize the solution.

Problem Description

// Given a sorted array of integers, your task is to implement a function
// `compressToDistinct` that modifies the array in-place to ensure
// it starts with a sequence of distinct elements in their original order.
// After making these modifications, the function should return
// the count of these distinct elements.

// The elements in the latter part of the array, after the distinct ones, are not important.

// Example:

// If the input array is [3, 3, 5, 7, 7, 8], there are four distinct elements: 3, 5, 7, and 8.
// After modifying the array to place these distinct elements at the beginning,
// the resulting array should look like this -> [3, 5, 7, 8, _, _].
// The underscores (_) represent the elements that are no longer important.

// You should name the function `compressToDistinct` for the tests to work correctly.

function testCompressToDistinct(array, expectedLength) {
  const originalReference = array;
  const resultLength = compressToDistinct(array);
  const isSameObject = originalReference === array;
  const isLengthCorrect = resultLength === expectedLength;
  const isModifiedCorrectly = array.slice(0, expectedLength).every((val, idx, arr) => idx === 0 || val > arr[idx - 1]);

  return isSameObject && isLengthCorrect && isModifiedCorrectly;
}

console.log(testCompressToDistinct([3, 3, 5, 7, 7, 8], 4));
console.log(testCompressToDistinct([1, 1, 2, 2, 2, 3, 4, 4, 5], 5));
console.log(testCompressToDistinct([0], 1));
console.log(testCompressToDistinct([-5, -3, -3, -1, 0, 0, 0, 1], 5));
console.log(testCompressToDistinct([6, 6, 6, 6, 6, 6, 6], 1));

// All tests should log true.

Walkthrough & Solution

You can use the anchor/runner pointer strategy where anchor starts at index 0, and runner starts at index 1.

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

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;
}