Forem: Whitney

Algorithm Techniques: Two Pointers

Whitney — Wed, 15 May 2024 15:53:44 +0000

What is the two pointers technique?

A more flexible variation of the sliding window technique, the two pointers used in this technique can move independently or in tandem through data structures.

When is this technique useful?

This is a common pattern that can be used in a wide range of algorithms. Each pointer refers to an index and travels through the array/string/linked list in order to solve a problem. If the problem requires finding pairs, a specific subsequence, or checking for a palindrome, consider using the two pointer technique.

In the examples below, two pointers are used to accomplish a variety of tasks.

Common examples:

Sorting Colors (with JS) This function uses two pointers to sort an array of integers in-place.

function sortColors(nums: number[]): void {
    // two pointers
    let left = 0, mid = 0;
    let right = nums.length - 1;

    while (mid <= right) {
        if (nums[mid] === 0) {
            [nums[left], nums[mid]] = [nums[mid], nums[left]];
            left++;
            mid++;
        } else if (nums[mid] === 2) {
            [nums[mid], nums[right]] = [nums[right], nums[mid]];
            right--;
        } else {
            mid++;
        }
    }
};

Merging Arrays In this simple array merging algorithm, a two pointers travel down two separate sorted arrays, while a third one inserts the larger of the pair. This maintains the nondecreasing order while merging.

function merge(nums1: number[], m: number, nums2: number[], n: number): void {
    let mPointer = m - 1;
    let nPointer = n - 1;
    let insertionInd = m + n - 1;

    while (nPointer >= 0) {
        if (nums1[mPointer] > nums2[nPointer]) {
            nums1[insertionInd] = nums1[mPointer];
            mPointer--;
        } else {
            nums1[insertionInd] = nums2[nPointer];
            nPointer--;
        }
        insertionInd--;
    }
};

Finding Palindromic Substrings Finally, two pointers are used in this example to identify palindromes. After successfully identifying one, the pointers move to the left and right sides to search for an even longer palindrome.

function countSubstrings(s: string): number {
    let count = 0;

    for (let i = 0; i < s.length; i++) {
        expand(i, i); // check for odd-length palindromes
        expand(i, i + 1); // check for even-length palindromes
    }
    return count;

    function expand(left, right) {
        while (left >= 0 && right < s.length && s[left] === s[right]) {
            count++;
            left--;
            right++;
        }
    }
};

Algorithm Techniques: Sliding Window

Whitney — Mon, 06 May 2024 23:49:47 +0000

What is the sliding window technique?

The sliding window is an algorithm method that iterates a range, or "window" through a sequential data structure. This is an efficient way to process elements using only one loop.

When is this technique useful?

As an alternative to nested loops, the sliding window can reduce the time complexity from O(n^2) to O(n). It is useful when solving problems that require finding a subrange or subsequence. For example, when finding a subarray with the highest sum or the longest substring without repeating characters.

Common problems this technique solves:

Finding the longest substring without repeating characters

// typescript solution:

function lengthOfLongestSubstring(s: string): number {
    let max = 0;
    let start = 0;
    const map = new Map();
    for (let i = 0; i < s.length; i++) {
        if (map.has(s[i])) {
            start = Math.max(map.get(s[i]) + 1, start);
        }
        map.set(s[i], i);
        max = Math.max(max, i - start + 1);
    }
    return max;
};

Finding the smallest subarray with a minimum sum

// typescript solution: 

function minSubArrayLen(target: number, nums: number[]): number {
  let minLength = Infinity;
  let left = 0, right = 0, sum = 0;

  while (right < nums.length) {
    sum += nums[right];

    while (sum >= target) {
        minLength = Math.min(minLength, right - left + 1);
        if (minLength === 1) return minLength; 
        sum -= nums[left];
        left++;
    }
    right++;
  }

  return minLength === Infinity ? 0 : minLength;
}

Minor Issues: Handling user events with Jest

Whitney — Mon, 06 May 2024 21:23:18 +0000

In an effort to document what I'm working on - and hopefully retain the information as well - I'll be documenting the tidbits that I learn. This includes only the information that I can share publicly, including my personal projects and open-source work. Feel free to make suggestions where you see fit!

Jest testing with React

Jest is a popular JavaScript testing framework known for unit and integration testing. This week I used Jest and React Testing Library to test an open-source codebase's reusable button component. Tests are being implemented retroactively and aim to better protect the codebase.

Most of my the button testing went smoothly. Testing for focus, however, proved to be a challenge.

Problem: Testing that a button doesn't trap focus

One test needed to assert that a "Tab" press would move focus from the button to the next element. At first, I tried using "fireEvent" to mimic a keyboard press of the Tab key. However, this did not affect the focus. I learned that fireEvent is not the best way to do this.

Solution: @testing-library/user-event

FireEvent can be used with Jest tests, but in most cases it is recommended to use @testing-library/user-event instead.

The @testing-library/user-event library mimics user interactions, accounts for accessibility best practices, and manages edge cases where fireEvent may not behave as expected - like in this case!

In this case, userEvent.tab() is all that was needed to successfully imitate a user hitting "Tab" on the keyboard.

test('Button does not trap focus', () => {
  const { getByRole, getByTestId } = render(
    <>
      <Button buttonText="Click me" />
      <input type="text" data-testid="next-element" />
    </>
  );

  const button = getByRole('button', { name: /Click me/i });
  const nextElement = getByTestId('next-element');

  button.focus();
  userEvent.tab();

  expect(nextElement).toHaveFocus();
});