Search in Rotated Sorted Array

Explore

EXPLORE THE CATALOGSupercharge your career with 700+ hands-on courses

View All Courses

Python

Java

JavaScript

React

Docker

Vue JS

Web Dev

DevOps

AWS

LEARNING TOOLSExplore the industry's most complete learning platform

CoursesLevel up your skills

Cloud LabsSetup-free practice with Cloud Services

Skill PathsAchieve learning goals

ProjectsBuild real-world applications

Mock InterviewsNewAI-Powered interviews

Personalized Interview PrepNewGet a custom roadmap tailored to your goals

AssessmentsBenchmark your skills

Personalized PathsGet the right resources for your goals

LEARN TO CODE

Check out our beginner friendly courses.

Pricing

For Business

Resources

NewsletterCurated insights on AI, Cloud & System Design

BlogFor developers, By developers

Free CheatsheetsDownload handy guides for tech topics

0% completed

All LessonsFree Lessons (186)

Getting Started

Course Overview Who Should Take This Course

Two Pointers

Mock interview

Two Pointers

Fast and Slow Pointers

Introduction to Fast and Slow Pointers Happy Number Solution: Happy Number Linked List Cycle Solution: Linked List Cycle Middle of the Linked List Solution: Middle of the Linked List Circular Array Loop Solution: Circular Array Loop Find the Duplicate Number Solution: Find the Duplicate Number Palindrome Linked List Solution: Palindrome Linked List Maximum Twin Sum of a Linked List Solution: Maximum Twin Sum of a Linked List Split a Circular Linked List Solution: Split a Circular Linked List Linked List Cycle III Solution: Linked List Cycle III

Mock interview

Fast and Slow Pointers

Sliding Window

Introduction to Sliding Window Repeated DNA Sequences Solution: Repeated DNA Sequences Sliding Window Maximum Solution: Sliding Window Maximum Minimum Window Subsequence Solution: Minimum Window Subsequence Longest Repeating Character Replacement Solution: Longest Repeating Character Replacement Minimum Window Substring Solution: Minimum Window Substring Longest Substring without Repeating Characters Solution: Longest Substring without Repeating Characters Minimum Size Subarray Sum Solution: Minimum Size Subarray Sum Maximum Average Subarray I Solution: Maximum Average Subarray I Diet Plan Performance Solution: Diet Plan Performance Fruit Into Baskets Solution: Fruit Into Baskets Contains Duplicate II Solution: Contains Duplicate II Frequency of the Most Frequent Element Solution: Frequency of the Most Frequent Element

Mock interview

Sliding Window

Heaps

K-way merge

Introduction to K-way Merge Merge Sorted Array Solution: Merge Sorted Array Kth Smallest Number in M Sorted Lists Solution: Kth Smallest Number in M Sorted Lists Find K Pairs with Smallest Sums Solution: Find K Pairs with Smallest Sums Merge K Sorted Lists Solution: Merge K Sorted Lists Kth Smallest Element in a Sorted Matrix Solution: Kth Smallest Element in a Sorted Matrix Kth Smallest Prime Fraction Solution: Kth Smallest Prime Fraction Super Ugly Number Solution: Super Ugly Number

Top K Elements

Introduction to Top K Elements Kth Largest Element in a Stream Solution: Kth Largest Element in a Stream Reorganize String Solution: Reorganize String K Closest Points to Origin Solution: K Closest Points to Origin Top K Frequent Elements Solution: Top K Frequent Elements Kth Largest Element in an Array Solution: Kth Largest Element in an Array Third Maximum Number Solution: Third Maximum Number Find Subsequence of Length K with the Largest Sum Solution: Find Subsequence of Length K with the Largest Sum Minimum Cost to Hire K Workers Solution: Minimum Cost to Hire K Workers Maximal Score After Applying K Operations Solution: Maximal Score After Applying K Operations Find the Kth Largest Integer in the Array Solution: Find the Kth Largest Integer in the Array

Modified Binary Search

Introduction to Modified Binary Search

Binary Search

Solution: Binary Search

Search in Rotated Sorted Array

Solution: Search in Rotated Sorted Array

First Bad Version

Solution: First Bad Version

Random Pick with Weight

Solution: Random Pick with Weight

Find K Closest Elements

Solution: Find K Closest Elements

Single Element in a Sorted Array

Solution: Single Element in a Sorted Array

Maximum Value at a Given Index in a Bounded Array

Solution: Maximum Value at a Given Index in a Bounded Array

The K Weakest Rows in a Matrix

Solution: The K Weakest Rows in a Matrix

Split Array Largest Sum

Solution: Split Array Largest Sum

Search in Rotated Sorted Array II

Mock interview

Modified Binary Search

Subsets

Introduction to Subsets Subsets Solution: Subsets Permutations Solution: Permutations Letter Combinations of a Phone Number Solution: Letter Combinations of a Phone Number Generate Parentheses Solution: Generate Parentheses Letter Case Permutation Solution: Letter Case Permutation Find K-Sum Subsets

Greedy Techniques

Introduction to Greedy Techniques Jump Game Solution: Jump Game Boats to Save People Solution: Boats to Save People Gas Station Solution: Gas Station Two City Scheduling Solution: Two City Scheduling Minimum Number of Refueling Stops Solution: Minimum Number of Refueling Stops Largest Palindromic Number Solution: Largest Palindromic Number Assign Cookies Solution: Assign Cookies Rearranging Fruits Solution: Rearranging Fruits Number of Steps to Reduce a Binary Number to One Solution: Number of Steps to Reduce a Binary Number to One Maximum Swap Solution: Maximum Swap Can Place Flowers Solution: Can Place Flowers Largest Odd Number in String Solution: Largest Odd Number in String Jump Game II Best Time to Buy and Sell Stock

Backtracking

Introduction to Backtracking N-Queens Solution: N-Queens Word Search Solution: Word Search House Robber III Solution: House Robber III Restore IP Addresses Solution: Restore IP Addresses Flood Fill Solution: Flood Fill Minimum Moves to Spread Stones Over Grid Solution: Minimum Moves to Spread Stones Over Grid Binary Tree Paths Solution: Binary Tree Paths Binary Watch Solution: Binary Watch Optimal Account Balancing Solution: Optimal Account Balancing Split a String Into the Max Number of Unique Substrings Solution: Split a String Into the Max Number of Unique Substrings Sudoku Solver Matchsticks to Square

Dynamic Programming

Introduction to Dynamic Programming 0/1 Knapsack Solution: 0/1 Knapsack Coin Change Solution: Coin Change N-th Tribonacci Number Solution: N-th Tribonacci Number Partition Equal Subset Sum Solution: Partition Equal Subset Sum Counting Bits Solution: Counting Bits 01 Matrix Solution: 01 Matrix House Robber II Solution: House Robber II Maximum Product Subarray Solution: Maximum Product Subarray Combination Sum Solution: Combination Sum Word Break Solution: Word Break Palindromic Substrings Solution: Palindromic Substrings Longest Common Subsequence Solution: Longest Common Subsequence Word Break II Solution: Word Break II Decode Ways Solution: Decode Ways Count the Number of Good Subsequences Solution: Count the Number of Good Subsequences Climbing Stairs

Mock interview

Dynamic Programming

Cyclic Sort

Introduction to Cyclic Sort Missing Number Solution: Missing Number First Missing Positive Solution: First Missing Positive Find the Corrupt Pair Solution: Find the Corrupt Pair Find the First K Missing Positive Numbers Sort Array By Parity II Solution: Sort Array By Parity II

Topological Sort

Introduction to Topological Sort Compilation Order Solution: Compilation Order Alien Dictionary Solution: Alien Dictionary Verifying an Alien Dictionary Solution: Verifying an Alien Dictionary Course Schedule II Solution: Course Schedule II Course Schedule Solution: Course Schedule Build a Matrix with Conditions Solution: Build a Matrix with Conditions Longest Path With Different Adjacent Characters Solution: Longest Path With Different Adjacent Characters Find All Possible Recipes from Given Supplies

Mock interview

Topological Sort

Sort and Search

Introduction to Sort and Search Find the Distance Value Between Two Arrays Solution: Find the Distance Value Between Two Arrays Longest Subsequence With Limited Sum Solution: Longest Subsequence With Limited Sum Find Target Indices After Sorting Array Solution: Find Target Indices After Sorting Array Count Pairs in Two Arrays Solution: Count Pairs in Two Arrays Valid Triangle Number Solution: Valid Triangle Number Minimum Operations to Make All Array Elements Equal Solution: Minimum Operations to Make All Array Elements Equal Sum of Mutated Array Closest to Target Solution: Sum of Mutated Array Closest to Target Range Sum of Sorted Subarray Sums Solution: Range Sum of Sorted Subarray Sums Magnetic Force Between Two Balls Solution: Magnetic Force Between Two Balls Find K-th Smallest Pair Distance Solution: Find K-th Smallest Pair Distance Minimum Space Wasted from Packaging Solution: Minimum Space Wasted from Packaging Russian Doll Envelopes Solution: Russian Doll Envelopes Two Sum Less Than K Maximum Number of Integers to Choose from a Range I

Matrices

Introduction to Matrices Set Matrix Zeroes Solution: Set Matrix Zeroes Rotate Image Solution: Rotate Image Spiral Matrix Solution: Spiral Matrix Where Will the Ball Fall Solution: Where Will the Ball Fall Transpose Matrix Solution: Transpose Matrix Count Negative Numbers in a Sorted Matrix Solution: Count Negative Numbers in a Sorted Matrix Minimum Time Takes to Reach Destination Without Drowning Solution:Minimum Time Takes to Reach Destination Without Drowning Island Perimeter Solution: Island Perimeter Convert 1D Array Into 2D Array Solution: Convert 1D Array Into 2D Array Spiral Matrix II Solution: Spiral Matrix II Flip Columns For Maximum Number of Equal Rows Solution: Flip Columns For Maximum Number of Equal Rows Number of Spaces Cleaning Robot Cleaned Solution: Number of Spaces Cleaning Robot Cleaned

Stacks

Introduction to Stacks Basic Calculator Solution: Basic Calculator Remove All Adjacent Duplicates In String Solution: Remove All Adjacent Duplicates In String Minimum Remove to Make Valid Parentheses Solution: Minimum Remove to Make Valid Parentheses Exclusive Time of Functions Solution: Exclusive Time of Functions Flatten Nested List Iterator Solution: Flatten Nested List Iterator Implement Queue Using Stacks Solution: Implement Queue Using Stacks Daily Temperatures Solution: Daily Temperatures Decode String Solution: Decode String Minimum String Length After Removing Substrings Solution: Minimum String Length After Removing Substrings Valid Parentheses

Graphs

Introduction to Graphs Network Delay Time Solution: Network Delay Time Paths in Maze That Lead to Same Room Solution: Paths in Maze That Lead to Same Room Clone Graph Solution: Clone Graph Graph Valid Tree Solution: Graph Valid Tree Bus Routes Solution: Bus Routes Reconstruct Itinerary Solution: Reconstruct Itinerary Find the Town Judge Solution: Find the Town Judge Find Center of Star Graph Solution: Find Center of Star Graph Lucky Numbers in a Matrix Solution: Lucky Numbers in a Matrix Path with Maximum Probability Solution: Path with Maximum Probability

Mock interview

Graphs

Tree Depth-First Search

Introduction to Tree Depth-First Search Flatten Binary Tree to Linked List Solution: Flatten Binary Tree to Linked List Diameter of Binary Tree Solution: Diameter of Binary Tree Serialize and Deserialize Binary Tree Solution: Serialize and Deserialize Binary Tree Invert Binary Tree Solution: Invert Binary Tree Binary Tree Maximum Path Sum Solution: Binary Tree Maximum Path Sum Convert Sorted Array to Binary Search Tree Solution: Convert Sorted Array to Binary Search Tree Build Binary Tree from Preorder and Inorder Traversal Solution: Build Binary Tree from Preorder and Inorder Traversal Binary Tree Right Side View Solution: Binary Tree Right Side View Lowest Common Ancestor of a Binary Tree Solution: Lowest Common Ancestor of a Binary Tree Validate Binary Search Tree Solution: Validate Binary Search Tree Nested List Weight Sum II Solution: Nested List Weight Sum II Inorder Successor in BST Solution: Inorder Successor in BST Height of Binary Tree After Subtree Removal Queries Solution: Height of Binary Tree After Subtree Removal Queries Delete Nodes And Return Forest Solution: Delete Nodes And Return Forest Maximum Depth of Binary Tree Kth Smallest Element in a BST

Tree Breadth-First Search

Introduction to Tree Breadth-First Search Binary Tree Level Order Traversal Solution: Binary Tree Level Order Traversal Binary Tree Zigzag Level Order Traversal Solution: Binary Tree Zigzag Level Order Traversal Populating Next Right Pointers in Each Node Solution: Populating Next Right Pointers in Each Node Vertical Order Traversal of a Binary Tree Solution: Vertical Order Traversal of a Binary Tree Symmetric Tree Solution: Symmetric Tree Word Ladder Solution: Word Ladder Two Sum IV – Input Is a BST Solution: Two Sum IV – Input Is a BST Connect All Siblings of a Binary Tree

Mock interview

Tree Breadth First Search

Trie

Introduction to Trie Implement Trie (Prefix Tree)Solution: Implement Trie (Prefix Tree)Search Suggestions System Solution: Search Suggestions System Replace Words Solution: Replace Words Design Add and Search Words Data Structure Solution: Design Add and Search Words Data Structure Word Search II Solution: Word Search II Top K Frequent Words Solution: Top K Frequent Words Longest Common Prefix Solution: Longest Common Prefix Index Pairs of a String Solution: Index Pairs of a String Lexicographical Numbers

Hash Maps

Introduction to Hash Maps Design HashMap Solution: Design HashMap Fraction to Recurring Decimal Solution: Fraction to Recurring Decimal Logger Rate Limiter Solution: Logger Rate Limiter Next Greater Element I Solution: Next Greater Element I Isomorphic Strings Solution: Isomorphic Strings Find Duplicate File in System Solution: Find Duplicate File in System Dot Product of Two Sparse Vectors Solution: Dot Product of Two Sparse Vectors High Five Solution: High Five Bulls and Cows Solution: Bulls and Cows Number of Wonderful Substrings Solution: Number of Wonderful Substrings Total Appeal of a String Solution: Total Appeal of a String Smallest Rectangle Enclosing Black Pixels Solution: Smallest Rectangle Enclosing Black Pixels Number of Distinct Islands Solution: Number of Distinct Islands Custom Sort String Solution: Custom Sort String Continuous Subarray Sum Solution: Continuous Subarray Sum Unique Number of Occurrences Solution: Unique Number of Occurrences Longest Palindrome

Knowing What to Track

Introduction to Knowing What to Track Palindrome Permutation Solution: Palindrome Permutation Valid Anagram Solution: Valid Anagram Design Tic-Tac-Toe Solution: Design Tic-Tac-Toe Group Anagrams Solution: Group Anagrams Maximum Frequency Stack Solution: Maximum Frequency Stack First Unique Character in a String Solution: First Unique Character in a String Find All Anagrams in a String Solution: Find All Anagrams in a String Longest Palindrome by Concatenating Two-Letter Words Solution: Longest Palindrome by Concatenating Two-Letter Words Pairs of Songs With Total Durations Divisible by 60 Solution: Pairs of Songs With Total Durations Divisible by 60 Rank Teams by Votes Solution: Rank Teams by Votes Minimum Number of Pushes to Type Word II Solution: Minimum Number of Pushes to Type Word II Task Scheduler Solution: Task Scheduler Ransom Note

Union Find

Introduction to Union Find Redundant Connection Solution: Redundant Connection Number of Islands Solution: Number of Islands Most Stones Removed with Same Row or Column Solution: Most Stones Removed with Same Row or Column Longest Consecutive Sequence Solution: Longest Consecutive Sequence Last Day Where You Can Still Cross Solution: Last Day Where You Can Still Cross Regions Cut by Slashes Solution: Regions Cut by Slashes Accounts Merge Solution: Accounts Merge Minimize Malware Spread Solution: Minimize Malware Spread The Skyline Problem Solution: The Skyline Problem Find if Path Exists in Graph Solution: Find if Path Exists in Graph Evaluate Division

Mock interview

Union Find

Custom Data Structures

Introduction to Custom Data Structures Snapshot Array Solution: Snapshot Array Time Based Key-Value Store Solution: Time Based Key-Value Store LRU Cache Solution: LRU Cache Insert Delete GetRandom O(1)Solution: Insert Delete GetRandom O(1)Min Stack Solution: Min Stack Range Module Solution: Range Module Shortest Word Distance II Solution: Shortest Word Distance II Max Stack Solution: Max Stack Design HashSet Solution: Design HashSet Moving Average from Data Stream Solution: Moving Average from Data Stream Two Sum III - Data structure design Solution: Two Sum III - Data structure design Range Sum Query - Immutable Solution: Range Sum Query - Immutable LFU Cache

Bitwise Manipulation

Introduction to Bitwise Manipulation Find the Difference Solution: Find the Difference Complement of Base 10 Integer Solution: Complement of Base 10 Integer Flipping an Image Solution: Flipping an Image Single Number Solution: Single Number Single Number II Solution: Single Number II Encode and Decode Strings Solution: Encode and Decode Strings Sum of All Subset XOR Totals Solution: Sum of All Subset XOR Totals Find The K-th Lucky Number Solution: Find The K-th Lucky Number Minimum Number of K Consecutive Bit Flips Solution: Minimum Number of K Consecutive Bit Flips Find the Longest Substring Having Vowels in Even Counts Solution: Find the Longest Substring Having Vowels in Even Counts Count Triplets That Can Form Two Arrays of Equal XOR Solution: Count Triplets That Can Form Two Arrays of Equal XOR Longest Subarray With Maximum Bitwise AND Solution: Longest Subarray With Maximum Bitwise AND Reverse Bits

Math and Geometry

Introduction to Math and Geometry Check If It Is a Straight Line Solution: Check If It Is a Straight Line Minimum Cuts to Divide a Circle Solution: Minimum Cuts to Divide a Circle Rectangle Overlap Solution: Rectangle Overlap Minimum Time Visiting All Points Solution: Minimum Time Visiting All Points Reverse Integer Solution: Reverse Integer Valid Square Solution: Valid Square Rectangle Area Solution: Rectangle Area Minimum Area Rectangle Solution: Minimum Area Rectangle Maximum Area Rectangle With Point Constraints I Solution: Maximum Area Rectangle With Point Constraints I Convex Polygon Solution: Convex Polygon Queries on Number of Points Inside a Circle Solution: Queries on Number of Points Inside a Circle Max Points on a Line Solution: Max Points on a Line Maximum Number of Visible Points Solution: Maximum Number of Visible Points Minimize Manhattan Distances Solution: Minimize Manhattan Distances Minimum Number of Lines to Cover Points Detonate the Maximum Bombs

Challenge Yourself

Challenge Yourself: Introduction Shortest Bridge Number of Connected Components in an Undirected Graph Median of Two Sorted Arrays Pacific Atlantic Water Flow Contains Duplicate Maximum Subarray Two Sum Find Minimum in Rotated Sorted Array Non-overlapping Intervals Meeting Rooms Largest Rectangle in Histogram Subtree of Another Tree Sort List Number of 1 Bits Container with Most Water Evaluate Reverse Polish Notation 4Sum Loud and Rich Product of Array Except Self Longest Increasing Subsequence Sum of Two Integers Majority Element Unique Paths Longest Palindromic Substring Permutations II Number of Provinces Linked List Cycle II Minimum Flips to Make the Binary String Alternate Lemonade Change House Robber Find All Numbers Disappeared in an Array Find All Duplicates in an Array Same Tree Design In-Memory File System Design File System Asteroid Collision Rotting Oranges Add Binary Multiply Strings

Conclusion

Where to Go from Here?

Mock interview

Coding Patterns

Practice Mock Interview

Grokking the Coding Interview Patterns in Go/

...

Search in Rotated Sorted Array

Try to solve the Search in Rotated Sorted Array problem.

We'll cover the following...

Statement
Examples
Understand the problem
Figure it out!
Try it yourself