Faangshui
Bootcamp Collection: Core Concepts
Practice problem set: Index Pointers (Two Pointers) Practice Problems
0/4 tasks

Index Pointers / Two Pointers Practice Problems

Difficulty level: White Belt

Below are some practice problems for Index Pointers/Two Pointers.

Follow this guide on Index Pointers/Two Pointers to learn more about the concept.

The Longest Stretch of Glory

In preparation for the temple’s Festival of Lights, the apprentices are tasked with inspecting the sacred light string. Each bulb is represented by 1 if it’s lit and 0 if it’s not. But there’s a catch — Chef Bao is offering extra dumplings to the apprentice who can find the longest stretch of glowing bulbs! Naturally, chaos ensues as everyone races to prove their skills.

Your task is to find the starting index of the longest stretch of consecutive glowing bulbs (1s). If multiple stretches have the same length, return the start of the first one. And if there are no glowing bulbs at all, you might as well go and help in the kitchen or just return -1.

Example Input:

lights = "11011101111"

Example Output:

7

To solve this task:

  1. Track the Start and Length:
    • Use a pointer variable start to track where a sequence of 1s begins.
    • Keep a variable max_length to store the maximum length of glowing bulbs found so far.
    • Use another variable max_start to remember the starting index of the longest stretch.
  2. Traverse the String:
    • For each bulb:
    • If it’s 1, check if it starts a new sequence or continues the current one.
    • If it’s 0, calculate the length of the previous sequence and update max_length and max_start if necessary.
  3. Handle the Final Sequence:
    • After the loop, check if the last sequence of glowing bulbs is the longest.
  4. Return the Result:
    • Return max_start, which holds the index of the longest stretch. If no bulbs are glowing, return -1—but don’t tell Chef Bao.
The Longest Stretch of Glory

The Great Scroll Hunt

Deep in the temple archives, three apprentices—Ada, Ren, and Jin—are tasked with finding a single scroll that appears in all three of their assigned sections. Each apprentice's section is sorted alphabetically, but they’re too lazy to compare everything manually. The scroll must be the smallest common element among their sections.

Write a function to find the smallest scroll (element) that appears in all three sorted arrays. If no such scroll exists, return -1 — and prepare to face Master Qu’s disapproving glare.

Example Input:

scrolls_a = [2, 3, 5, 8, 10]
scrolls_b = [4, 5, 6, 10, 12]
scrolls_c = [1, 2, 3, 5, 10, 15]

Example Output:

5

To solve this task:

  1. Use Three Pointers:
    • Start with a pointer for each array (i, j, and k for arrays A, B, and C respectively).
    • Initialize all pointers to 0.
  2. Traverse the Arrays Simultaneously:
    • Compare the elements at the current pointer positions:
      • If the elements are equal, you’ve found the smallest common scroll. Return it.
      • Otherwise, increment the pointer for the smallest element to "catch up."
  3. Handle Edge Cases:
    • If any pointer exceeds the length of its array, there’s no common element. Return -1.
The Great Scroll Hunt

Scrolls of Order

In the bustling archives of the Faangshui Temple, apprentices are tasked with organizing scrolls marked with positive and negative values. To make things easier for Master Kwan, all scrolls with negative values must be shifted to the left side of the shelf. The relative order of all elements must be maintained.

Write a function to rearrange an array such that all negative numbers move to the left side. The rearrangement must be done in-place without using extra space.

Example Input:

scrolls = [1, -2, 3, -4, 5, -6]

Example Output:

[-2, -4, -6, 1, 3, 5]

To solve this task:

  1. Use Fast and Slow Pointers:
    • One pointer (slow) starts at the beginning of the array and tracks where the next negative number should be placed.
    • The second pointer (fast) traverses the array.
  2. Traverse and Swap:
    • If the current element is negative, swap it with the element at the slow pointer.
    • Increment the slow pointer after each swap to ensure negatives are placed in order.
  3. In-Place Rearrangement:
    • Perform swaps directly within the array to avoid using extra space.
  4. Edge Cases:
    • If the array is empty, do nothing.
    • If there are no negative numbers, the array should remain unchanged.
Scrolls of Order

Sorting the Scrolls by Strength

Master Quan has a peculiar request. He insists on squaring the strength values of the scrolls and then sorting them in ascending order. However, the scroll strengths are already sorted by their original values, both negative and positive. The challenge is to rearrange the squared values efficiently, without simply sorting the resulting array from scratch.

Write a function to take a sorted array of integers, square each value, and return a new array of the squared values sorted in ascending order.

Example Input:

scrolls = [-4, -2, 0, 3, 5]

Example Output:

[0, 4, 9, 16, 25]

To solve this task efficiently:

  1. Use Converging Pointers:
    • Start with one pointer at the beginning of the array (left) and another at the end (right).
    • The largest square will always come from either the smallest negative number (squared) or the largest positive number.
  2. Fill the Result Array Backwards:
    • Create a new array to hold the squared values in sorted order.
    • Compare the absolute values at left and right.
    • Place the larger square at the current end of the result array and move the corresponding pointer inward.
  3. Iterate Until Pointers Meet:
    • Repeat the comparison and placement until the two pointers cross.
  4. Efficiency:
    • This approach runs in O(n) time, leveraging the sorted order of the input array.
Sorting the Scrolls by Strength