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

Grokking Grind 75 in Python: 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.

# Statement

You're given an integer array, `arr`. Return a resultant array so that `res[i]` is equal to the product of all the elements of `arr` except `arr[i]`.


Write an algorithm that runs in $O(n$) time without using the division operation.

**Constraints:**

- $2 \leq$ `arr.length` $\leq 10^5$
- $-30 \leq$ `arr[i]` $\leq 30$
- The product of any prefix or suffix of `arr` is guaranteed to fit in a 32-bit integer.

# Solution

So far, you have probably brainstormed some approaches and have an idea of how to solve this problem. Let’s explore some of these approaches and figure out which one to follow based on considerations such as time complexity and any implementation constraints.

## Naive approach

A naive approach would be to use nested loops to traverse the array. For each element, we traverse all the other elements and calculate their product, which will be stored in the corresponding index of the output array.

The time complexity of this approach is $O(n^2)$, since we're using nested loops to traverse the array. The space complexity of this approach is $O(1)$, since we're using a constant number of additional variables.

## Optimized approach using Two Pointers

The idea is that we can break down the problem into two parts: the product of elements to the left of each index and the product of elements to the right of each index. By maintaining two separate running products as we traverse the array from both ends, we can accumulate the product values to populate the `res` array. This approach eliminates the need for repeated multiplications and effectively calculates the product except for the element at the current index. The Two Pointers pattern is employed here to handle both the left and right products in a single traversal.

Here's how the algorithm works:

- Initialize the following variables that will assist us in performing the algorithm:

   - `res`: This array will be used to store the output. It is initialized to $1$.

   - `l`, `r`: These are the pointers used to traverse the array. They are initialized to the left and right ends of the array, respectively.

   - `left_product`: This variable stores the product of the elements to the left of the `l` pointer.

   - `right_product`: This variable stores the product of the elements to the right of the `r` pointer.

- Traverse the array while the `l` and `r` pointers are not out of bounds:

   - Calculate the product to the left of `nums[l]` and store it in `res[l]` using the following formula: 

      ```
      res[l] = res[l] * left_product
      ```


   - Calculate the product to the right of the `nums[r]` and store it in `res[r]` using the following formula: 

      ```
      res[r] = res[r] * right_product
      ```

   - Update `left_product` to include the current element, `nums[l]`, in the accumulated product for the next iteration.

   - Update `right_product` to include the current element, `nums[r]`, in the accumulated product for the next iteration.  

   - Finally, increment the `l` pointer and decrement the `r` pointer to evaluate the next elements. 

   - The steps above are repeated until the `l` and `r` pointers go out of bounds.

    >- When `l == r`, both pointers point to the middle element of the array. For this element, both the products to its left and right are being computed one after another and stored in `res[l]` (or `res[r]` since `l == r` in this case). Therefore, for the case of the middle element, the final product of all the elements, excluding it, is computed in one step.
   >
   >- After the `l` and `r` pointers cross each other, the following behavior occurs:
   >- The `l` pointer computes the product to the left of `nums[l]` as expected, but now the product to the right of `nums[l]` has already been computed in a previous iteration by the `r` pointer. Now both the right and left products have been calculated and combined, the resultant product in this entry is the final product of all the elements, excluding the current one. 
   >
   >- The `r` pointer computes the product to the right of `nums[r]` as expected, but now the product to the left of `nums[r]` has already been computed in a previous iteration by the `l` pointer. Now both the right and left products have been calculated and combined, the resultant product in this entry is the final product of all the elements, excluding the current one. 

- Lastly, the `res` array contains the desired result, so return it.

The slides below illustrate how the algorithm runs:



    


















Let's solve the Product of Array Except Self problem using the Two Pointers pattern.

Warming Up

Two Pointers

Fast and Slow Pointers

Modified Binary Search

Conclusion

Solution: Product of Array Except Self

Statement