Skip to content

LC-33-search-in-rotated-sorted-array.md

Latest commit

 

History

History
195 lines (145 loc) · 3.36 KB

LC-33-search-in-rotated-sorted-array.md

File metadata and controls

195 lines (145 loc) · 3.36 KB

24 - Search in Rotated Sorted Array

Jira Ticket: LND-143
LeetCode: https://leetcode.com/problems/search-in-rotated-sorted-array
Pattern: Binary Search
Difficulty: Medium
Status: To Do
Priority: Medium

Labels: Binary_Search, Medium
Created: 2025-08-21
Last Updated: 2025-08-22

📝 Problem Statement

Problem URL: https://leetcode.com/problems/search-in-rotated-sorted-array Problem Description: There is an integer array nums sorted in ascending order (with distinct values). Prior to being passed to your function, nums is possibly rotated at an unknown pivot index k (1 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). For example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2]. Given the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums. You must write an algorithm with O(log n) runtime complexity. Example 1: Input: nums = [4,5,6,7,0,1,2], target = 0 Output: 4 Example 2: Input: nums = [4,5,6,7,0,1,2], target = 3 Output: -1 Example 3: Input: nums = [1], target = 0 Output: -1 Constraints: 1 <= nums.length <= 5000 -10^4 <= nums[i] <= 10^4 All values of nums are unique. nums is an ascending array that is possibly rotated. -10^4 <= target <= 10^4 Difficulty: Medium Category: Binary Search

🤔 Initial Thoughts

Understanding the Problem

  • What are we asked to find/compute?
  • What are the inputs and outputs?
  • What are the edge cases?

Pattern Recognition

Why Binary Search?

What clues in the problem point to this pattern?

💡 Approach

Brute Force (if applicable)

Idea:

Time Complexity: O(?)
Space Complexity: O(?)

Optimized Approach

Idea:

Algorithm Steps: 1. 2. 3.

Time Complexity: O(?)
Space Complexity: O(?)

🎨 Visual Explanation

Example: 

Step 1: 
Step 2: 
Step 3:

💻 Implementation

# Your solution here
def solution():
    pass

Code Explanation

🧪 Test Cases

Test Case 1: Basic Example

Input: 
Expected Output: 
Actual Output: 
Status: ⏳ Not Tested

Test Case 2: Edge Case - Empty Input

Input: 
Expected Output: 
Actual Output: 
Status: ⏳ Not Tested

Test Case 3: Edge Case - Single Element

Input: 
Expected Output: 
Actual Output: 
Status: ⏳ Not Tested

📊 Complexity Analysis

Time Complexity: O(?)

Breakdown:

Space Complexity: O(?)

Breakdown:

🎓 Key Learnings

What I Learned

Mistakes I Made

Pattern Insights

  • When to use binary search:
  • When NOT to use this pattern:

🔗 Similar Problems

📚 Resources

✅ Progress Checklist

  • Problem understood
  • Pattern identified
  • Brute force solution
  • Optimized solution
  • All test cases pass
  • Complexity analyzed
  • Code reviewed
  • Learnings documented
  • Jira ticket updated

Status: 🔴 Not Started
Last Updated: 2025-08-22