Learn and practice the Two Pointers, Fast and Slow Pointers, and Modified Binary Search patterns to solve coding interview problems.

Grokking Grind 75 in JavaScript: Mastery through Coding Patterns

Mastering the fundamentals of programming and problem-solving is the first step towards effectively addressing a diverse range of challenges. This module covers foundational programming skills such as basic math operations, string manipulation, and data type conversions. Additionally, it helps us understand the significance of carefully reading and comprehending problem statements because sometimes it’s all about spotting hidden details, special rules, or unusual situations mentioned in them. The module also explores common problem-solving patterns for linear input data: Two Pointers, Fast and Slow Pointers, and Modified Binary Search. These patterns efficiently reduce the search space, following a divide-and-conquer approach. By the end of the module, we’ll have a solid foundation in programming and problem-solving techniques to address various challenges.

Two Pointers & Co.

# Understand the problem

Let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

Given the input `nums = [0]`, what will the array look like after sorting?

Given the input <code>nums = [0]</code>, what will the array look like after sorting?

Given the input `nums = [2, 2, 2]`, what will the array look like after sorting?

Given the input <code>nums = [2, 2, 2]</code>, what will the array look like after sorting?

Given the input `nums = [1, 1, 0, 0, 2, 2, 1, 0]`, what will the array look like after sorting?

Given the input <code>nums = [1, 1, 0, 0, 2, 2, 1, 0]</code>, what will the array look like after sorting?

Given the input `nums = [2, 1, 2, 0, 0, 1, 0, 2, 1, 1, 2, 0, 1, 0, 2]`, how many elements of each color ($0$, $1$, $2$) are in the sorted result?

Given the input <code>nums = [2, 1, 2, 0, 0, 1, 0, 2, 1, 1, 2, 0, 1, 0, 2]</code>, how many elements of each color (<math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mn>0</mn></mrow><annotation encoding="application/x-tex">0</annotation></semantics></math>0, <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mn>1</mn></mrow><annotation encoding="application/x-tex">1</annotation></semantics></math>1, <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mn>2</mn></mrow><annotation encoding="application/x-tex">2</annotation></semantics></math>2) are in the sorted result?

Given the input `nums = [0, 1, 0, 1, 0, 1]`, what will the array look like after sorting?

Given the input <code>nums = [0, 1, 0, 1, 0, 1]</code>, what will the array look like after sorting?

Sort Colors

Sort Colors

# Figure it out!

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Suppose your scan pointer meets a `0`, i.e., a red color, at index `i`. What is the earliest index that `0` could safely live in once the array is fully sorted?

The earliest safe spot is whatever index the left boundary currently marks.

Swap the `0` into that slot immediately; then bump the left boundary forward so the next `0` has a new home.

**Bonus insight:** this guarantees every `0` crosses each index at most once.

When you swap a `2` with the value at the right boundary, the cursor stays on the same index. Why bother re-examining that index instead of moving on?

Because the value you just pulled in from the right is still unknown—it might be a `0` that needs another move.

By re-checking, the algorithm ensures each element is handled exactly once without missing any rescues.

Your pointers move left → right, the right boundary moves right → left, and eventually they’ll meet.

Which condition tells you every element has been placed and it’s safe to stop?

Stop when the cursor is > right boundary. At that instant, everything left of the cursor holds only `0`s and `1`s, everything right of the boundary holds only `2`s, and the region between them has been fully processed.

# Quick Fix\nYou are Edward, a Senior Software Engineer who specializes in coding interview patterns, data structures and algorithms, and is great at debugging issues in code.\n\n- Edward, please keep in mind that you do not have to print the data of the placeholders. Also, do not mention anything about yourself.\n\nEdward, you are given the following data in the placeholders:\n- Function name: `sortColors`\n- Candidate's submitted solution code: USER_CODE\n- Error: ERROR_DESCRIPTION\n- Failed test case: FAILED_TEST_CASE\n- Coding language: `JavaScript`\n\n- Edward, your task is to understand the type of error that is occurring in the coding language provided.\n- Once you've understood the error as per the error’s description, and why the test case failed, you will suggest how the candidate can improve their solution code to fix the error.\n- Edward, you will not give the corrected code, just a hint on what the error tells, and how to fix it.\n- Edward, please limit your response strictly to 100 words. No more words than the limit.

# Review Code\nEdward, your current task is to review the `sortColors` function(s) and the other function(s) invoked in it/them.\n\n-Take your time and review the candidate's solution code.\n- Do not review any extra/helper files or functions not invoked in the solution function `sortColors`.\n- Do not review the code of data structure objects instantiated like a binary tree, linked list, trie, union find, etc., in the solution functions. Just review the solution/algorithm function of the problem. \n- Also, if the solution code doesn’t use the coding pattern stated above, then please encourage the candidate to reattempt the problem using that pattern corectly.

# Review time complexity\n- Please provide a brief time complexity analysis of the function(s) `sortColors`. \n- While calculating time complexity, include the time complexity of built-in JavaScript functions invoked by the code. \n- The answer should be to the point in approximately 60 words.

# Review space complexity\n- Please provide a brief space complexity analysis of the function(s) `sortColors`. \n- While calculating space complexity, include the space complexity of built-in JavaScript functions invoked by the code. \n- Do not include the space used for the input parameters and the space used for just returning an output (not used as a scratch space). \n- The answer should be to the point in approximately 60 words.

def evaluate_results(self) -> object:
 """
 self.__inputs is the list of inputs that are passed as input to function
 self.__actual_output is a list of outputs that is produced by the learner's code
 return : self.__edu__result object
 """
 def sort_colors(colors):
 red, white, blue = 0, 0, len(colors) - 1
 
 while white <= blue:
 if colors[white] == 0:
 if colors[red] != 0:
 colors[red], colors[white] = colors[white], colors[red]
 
 white += 1
 red += 1

 elif colors[white] == 1:
 white += 1

 else:
 if colors[blue] != 2:
 colors[white], colors[blue] = colors[blue], colors[white]

 blue -= 1

 return colors
 



 # multiple outputs will be added at each index respectively for a single test_case
 expected_outputs = [] 
 expected = sort_colors(self.__inputs[0])
 actual = self.__actual_outputs[0]
 # store the 1st expected output that should be displayed to the user 
 expected_outputs.append(expected) 
 if expected == actual:
 self.__edu_result.store_result(expected_outputs, TestCaseResult.PASS)
 else:
 self.__edu_result.store_result(expected_outputs, TestCaseResult.FAIL)

 return self.__edu_result

function sortColors(colors){

    // Replace this placeholder return statement with your code

    return colors;
}

export { sortColors }

index.yaml

testcases:
  - name: "Test Case 1 (EC1 - mixed three colors, moderate size)"
    inputs:
      - 1: [2, 0, 1, 2, 1, 0, 2, 1, 0, 1]
    output:
      - 1: [0, 0, 0, 1, 1, 1, 1, 2, 2, 2]
  - name: "Test Case 2 (EC3 - single element)"
    inputs:
      - 1: [1]
    output:
      - 1: [1]
  - name: "Test Case 3 (EC6 - reverse sorted)"
    inputs:
      - 1: [2, 2, 2, 1, 1, 0, 0, 0]
    output:
      - 1: [0, 0, 0, 1, 1, 2, 2, 2]
  - name: "Test Case 4 (EC7 - two distinct colors only)"
    inputs:
      - 1: [2, 0, 2, 0, 2, 0, 0]
    output:
      - 1: [0, 0, 0, 0, 2, 2, 2]
  - name: "Test Case 5 (EC8 - two-element wrong order)"
    inputs:
      - 1: [2, 0]
    output:
      - 1: [0, 2]

def sum(input_1, input_2):
    return input_1+input_2

def validate_inputs(self) -> None:
 """
 self.__inputs is the list of inputs that are passed as input to the function.
 Store the result using the self.store_result(error_msg, status).
 Return: void
 """
 def is_valid_1d_array(arr):
 if not isinstance(arr, list):
 return False # Not a valid 1D array if it's not a list
 
 return all(isinstance(elem, int) and not isinstance(elem, bool) for elem in arr)

 # Inputs can be accessed using self.__inputs starting from 0 to len(self.__inputs) - 1
 if not is_valid_1d_array(self.__inputs[0]):
 self.store_result(("Invalid test case."), ValidationFunction.FAIL)
 elif len(self.__inputs[0]) < 1 or len(self.__inputs[0]) > 300:
 self.store_result("Length of array should be between 1 and 300", ValidationFunction.FAIL)
 elif any(x not in [0, 1, 2] for x in self.__inputs[0]):
 self.store_result("Array can only contain 0s, 1s and 2s.", ValidationFunction.FAIL)
 else:
 self.store_result("", ValidationFunction.PASS)

Sort Colors

Statement

Examples

Understand the problem

Figure it out!

Try it yourself