LaunchSchool: An online school for Software Engineers

function reverseConsonants(str) {
  const vowels = new Set(['a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U']);
  const consonants = [];

  for (let char of str) {
    if (/[a-zA-Z]/.test(char) && !vowels.has(char)) {
      consonants.push(char);
    }
  }

  consonants.reverse();

  let result = '';
  let consonantIndex = 0;

  for (let char of str) {
    if (/[a-zA-Z]/.test(char) && !vowels.has(char)) {
      result += consonants[consonantIndex++];
    } else {
      result += char;
    }
  }

  return result;
}

High Level

For this solution, we'll use the start-end pointer strategy. Our start pointer will move to towards the end of the string looking for consonants while our end pointer will move towards the beginning looking for consonants. Once each pointer has found a consonant, we'll swap those characters. Once start and end meet, we know we've processed the whole string.

Algorithm

We can define a helper function to check whether a character is a consonant. The toLowerCase() string method will be helpful for making this case-insensitive.

In the main function, we can follow these steps:

1. Split the string into an array of characters.
2. initialize start and end pointers to the beginning and end of the string, respectively.
3. Move the start pointer to the right until we find a consonant.
4. Move the end pointer to the left until we find a consonant.
5. Swap the characters at start and end once both pointers are pointing to consonant characters.
6. Increment start by 1 and decrement end by 1, so that we don't swap the same pair again.
7. Repeat steps 3-6 until the start pointer becomes either equal to or greater than the end pointer. Once that happens, the reversal process is completed, and we can join the array and return the reversed string.

Time Complexity

Since we are making only one pass through the string, the time complexity is O(N).

Space Complexity

In this solution, we convert the string into an array of characters so that we can swap characters in place. This means the solution requires O(N) space, where N is the length of the string.

Walkthrough

Let's go through the example string HELLO step by step.

Step 1: In the first step we are splitting the string into an array of characters and initializing two pointers start (s) at index 0, and end (e) at index 4.

Step 2: In the second step, we move the start pointer (s) until it reaches a consonant character. Since it is already pointing at a consonant, 'H', it remains where it is.

Step 3: Next, we move the end pointer (e) until it reaches a consonant character. We only have to decrement once and we reach 'L'.

Step 4: Now, when both pointers point to consonants, we swap those consonants.

Step 5: After swapping, we increment the start pointer by 1 and decrement the end pointer by 1.

Step 6: We repeat the process. First, we move the start pointer (s) until it reaches a consonant character. We increment it once to reach 'L'.

Step 7: Next, we would move the end pointer (e) until it reaches a consonant character. It's already pointing to 'L', so we leave it where it is.

Step 8: In the final step, both pointers point to consonants. However, since start and end pointers are equal, this means we are done with the reversal process, and we can join the array back into the string and return the reversed string.

Solution Code

const isConsonant = (char) => {
  return "bcdfghjklmnpqrstvwxyz".includes(char.toLowerCase());
};

function reverseConsonants(str) {
  let chars = str.split("");
  let s = 0;
  let e = str.length - 1;

  while (s < e) {
    if (!isConsonant(chars[s])) {
      s++;
      continue;
    }
    if (!isConsonant(chars[e])) {
      e--;
      continue;
    }
    [chars[s], chars[e]] = [chars[e], chars[s]];
    s++;
    e--;
  }

  return chars.join("");
}

Here's our brute-force solution:

function compressToDistinct(arr) {
  if (arr.length === 0) return 0;

  const distinct = [];

  for (let i = 0; i < arr.length; i++) {
    if (i === 0 || arr[i] !== arr[i - 1]) {
      distinct.push(arr[i]);
    }
  }

  // Copy back to original array
  for (let i = 0; i < distinct.length; i++) {
    arr[i] = distinct[i];
  }

  return distinct.length;
}

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