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 are given a sorted integer array, `nums`, and an integer, `target`. The array may have been rotated by an arbitrary number. Your task is to find and return the index of `target` in this array. If `target` does not exist, return -1.

An original sorted array before rotation is given below:


digraph g {
    rankdir = "TB"  
    splines = false;
    bgcolor = transparent
    node[shape = record, fontname = "courier", fontsize="18"];
  size = "9"
    bgcolor = "transparent"
    array[label = <<table border="0" cellborder="1" cellspacing="0"> \
 
        <tr> \
            <td height="35" width="45" port="e1" bgcolor="#FFDC5C" >1</td>\ 
            <td height="35" width="45" port="e0" bgcolor="#FFDC5C" >10</td>\
            <td height="35" width="45" port="e2" bgcolor="#FFDC5C" >20</td> \ 
            <td height="35" width="45" port="e3" bgcolor="#FFDC5C" >47</td> \ 
            <td height="35" width="45" port="e4" bgcolor="#FFDC5C" >59</td> \ 
            <td height="35" width="45" port="e5" bgcolor="#FFDC5C" >63</td> \ 
            <td height="35" width="45" port="e6" bgcolor="#FFDC5C" >75</td> \ 
            <td height="35" width="45" port="e7" bgcolor="#FFDC5C" >88</td> \ 
            <td height="35" width="45" port="e8" bgcolor="#FFDC5C" >99</td> \ 
            <td height="35" width="45" port="e9" bgcolor="#FFDC5C" >107</td> \
            <td height="35" width="45" port="e10" bgcolor="#FFDC5C">120</td> \
            <td height="35" width="45" port="e11" bgcolor="#FFDC5C">133</td> \
            <td height="35" width="45" port="e12" bgcolor="#FFDC5C">155</td> \
            <td height="35" width="45" port="e13" bgcolor="#FFDC5C">162</td> \
            <td height="35" width="45" port="e14" bgcolor="#FFDC5C">176</td> \
            <td height="35" width="45" port="e15" bgcolor="#FFDC5C">188</td> \
            <td height="35" width="45" port="e16" bgcolor="#FFDC5C">199</td> \
            <td height="35" width="45" port="e17" bgcolor="#FFDC5C">200</td> \
            <td height="35" width="45" port="e18" bgcolor="#FFDC5C">210</td> \
            <td height="35" width="45" port="e19" bgcolor="#FFDC5C">222</td> \
        </tr> \
    </table>> shape=none];
    
 }

After rotating this array 6 times, it changes to:


digraph g {
    rankdir = "TB"  
    splines = false;
    bgcolor = transparent
    node[shape = record, fontname = "courier", fontsize="18"];
  size = "9"
    bgcolor = "transparent"
    array[label = <<table border="0" cellborder="1" cellspacing="0"> \
 
        <tr> \
 						<td height="35" width="45" port="e0" bgcolor="#33CFFF">176</td>\
            <td height="35" width="45" port="e0" bgcolor="#33CFFF" >188</td>\
            <td height="35" width="45" port="e2" bgcolor="#33CFFF" >199</td> \ 
            <td height="35" width="45" port="e3" bgcolor="#33CFFF" >200</td> \ 
            <td height="35" width="45" port="e4" bgcolor="#33CFFF" >210</td> \ 
            <td height="35" width="45" port="e5" bgcolor="#33CFFF" >222</td> \ 
            <td height="35" width="45" port="e6" bgcolor="#FFDC5C" >1</td> \ 
            <td height="35" width="45" port="e7" bgcolor="#FFDC5C" >10</td> \ 
            <td height="35" width="45" port="e8" bgcolor="#FFDC5C" >20</td> \ 
            <td height="35" width="45" port="e9" bgcolor="#FFDC5C" >47</td> \
            <td height="35" width="45" port="e10" bgcolor="#FFDC5C">59</td> \
            <td height="35" width="45" port="e11" bgcolor="#FFDC5C">63</td> \
            <td height="35" width="45" port="e12" bgcolor="#FFDC5C">75</td> \
            <td height="35" width="45" port="e13" bgcolor="#FFDC5C">88</td> \
            <td height="35" width="45" port="e14" bgcolor="#FFDC5C">99</td> \
            <td height="35" width="45" port="e15" bgcolor="#FFDC5C">107</td> \
            <td height="35" width="45" port="e16" bgcolor="#FFDC5C">120</td> \
            <td height="35" width="45" port="e17" bgcolor="#FFDC5C">133</td> \
            <td height="35" width="45" port="e18" bgcolor="#FFDC5C">155</td> \
            <td height="35" width="45" port="e18" bgcolor="#FFDC5C">162</td> \
        </tr> \
    </table>> shape=none];
    
 }

**Constraints**

- All values in `nums` are unique.
- The values in `nums` are sorted in ascending order.
- The array may have been rotated by some arbitrary number.
- $1 \leq$ `nums.length` $\leq 1000$
- $-10^4 \leq$ `nums[i]` $\leq 10^4$
- $-10^4 \leq$ `target` $\leq 10^4$

# Examples

Try to solve the Search in Rotated Sorted Array problem.

Warming Up

Two Pointers

Fast and Slow Pointers

Modified Binary Search

Conclusion

Search in Rotated Sorted Array

Statement