Ask LSBot
Back to Open Book Shelf

It's time to apply what you've learned about pointer-based techniques by solving some problems independently. As always, feel free to reference the walkthroughs if you get stuck.

Exercises

  1. We'll use the techniques learned so far in this section to solve the "Reverse Consonants" problem. First, try to solve it using a naive (brute-force) approach.

    // Given a string `str`, reverse all the consonants in the
// string and return it. Consonants are all alphabetic characters
// except for the vowels `'a'`, `'e'`, `'i'`, `'o'`, and `'u'`,
// which can appear in both lower and upper cases.
// The consonants can appear more than once in the string.

console.log(reverseConsonants("") === "");
console.log(reverseConsonants("s") === "s");
console.log(reverseConsonants("HELLO") === "LELHO");
console.log(reverseConsonants("leetcode") === "deectole");
console.log(reverseConsonants("example") === "elapmxe");
console.log(reverseConsonants("Consonants") === "sotnonasnC");

// All test cases should log true

    View Our Solution

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

  2. Now, try to write an optimized solution for "Reverse Consonants" using a pointer-based technique.

    Use start-end pointer strategy.

    The easiest way to find consonants is to create a string with all consonants and check whether the character is included in that string.

    View Our Solution

    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("");
}

  3. Let's now try another pointer based problem, "Compress to Distinct." Let's again start by solving it with a brute-force solution.

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

    View Our Solution

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

  4. Now, try to write an optimized solution for "Compress to Distinct" using a pointer-based technique.

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

    View Our Solution

    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;
}
Previous:  Two Pointers: Anchor/Runner
Next:  Intro to Binary Search

Ask LSBot about: Practice: Two Pointers

Your questions are private and won't be used to evaluate your performance.

×
This conversation with LSBot is temporary. Sign up for free to save your conversations with LSBot.

Hi! I'm LSBot. I'm here to help you understand this chapter content with fast, focused answers.

Ask me about concepts, examples, or anything you'd like clarified from this chapter. I can explain complex topics, provide examples, or help connect ideas.

Want to know more? Refer to the LSBot User Guide.

Practice: Two Pointers - Exercise

Your questions are private and won't be used to evaluate your performance.

×
This conversation with LSBot is temporary. Sign up for free to save your conversations with LSBot.

Hi! I'm LSBot. I'm here to help you think through this exercise by providing hints and guidance, without giving away the solution.

You can ask me about your approach, request clarification on the problem, or seek help when you feel stuck.

Want to know more? Refer to the LSBot User Guide.