Search Blogs

Showing results for "Pivot"

Found 6 results

LeetCode 2161: Partition Array According to Given Pivot – Java Easy Stable Partition Solution

IntroductionLeetCode 2161 is a clean and important array manipulation problem that tests:Array traversalStable partitioningOrder preservationTwo-pass and three-pass approachesLogical grouping of elementsThe interesting part of this problem is that we are not only partitioning the array around a pivot, but we also need to preserve the relative order of elements.This makes the problem slightly different from classical partition algorithms like QuickSort partitioning.In this article, we will understand:The intuition behind stable partitioningWhy order preservation mattersStep-by-step explanationDry runTime and space complexityComplete optimized Java solutionProblem StatementTry this probelm here :- Partition ArrayYou are given:An integer array:numsAn integer:pivotYou must rearrange the array such that:All elements smaller than pivot come firstAll elements equal to pivot come nextAll elements greater than pivot come lastRelative ordering must remain preservedReturn the rearranged array.ExampleInputnums = [9,12,5,10,14,3,10]pivot = 10Output[9,5,3,10,10,12,14]ExplanationElements less than 109, 5, 3Elements equal to 1010, 10Elements greater than 1012, 14All relative orderings are preserved.Key ObservationWe do NOT need sorting.We only need grouping while maintaining original order.This is called:Stable PartitioningApproachWe create a new array and fill it in 3 phases:Phase 1Insert all elements:< pivotPhase 2Insert all elements:== pivotPhase 3Insert all elements:> pivotThis naturally preserves relative ordering because we traverse left-to-right every time.Optimized Java Solutionclass Solution { public int[] pivotArray(int[] nums, int pivot) { int[] ans = new int[nums.length]; int index = 0; // Smaller than pivot for(int i = 0; i < nums.length; i++) { if(nums[i] < pivot) { ans[index] = nums[i]; index++; } } // Equal to pivot for(int i = 0; i < nums.length; i++) { if(nums[i] == pivot) { ans[index] = nums[i]; index++; } } // Greater than pivot for(int i = 0; i < nums.length; i++) { if(nums[i] > pivot) { ans[index] = nums[i]; index++; } } return ans; }}Step-by-Step ExplanationStep 1: Create Answer Arrayint[] ans = new int[nums.length];Stores final partitioned result.Step 2: Insert Smaller Elementsif(nums[i] < pivot)All smaller elements go first.Step 3: Insert Equal Elementsif(nums[i] == pivot)Pivot values are placed in the middle.Step 4: Insert Larger Elementsif(nums[i] > pivot)Larger elements go to the end.Dry RunInputnums = [9,12,5,10,14,3,10]pivot = 10Pass 1: Smaller ElementsAdd:9, 5, 3Current array:[9,5,3]Pass 2: Equal ElementsAdd:10, 10Current array:[9,5,3,10,10]Pass 3: Greater ElementsAdd:12, 14Final array:[9,5,3,10,10,12,14]Time ComplexityWe traverse the array 3 times.Time ComplexityO(N)Because:3N → O(N)Space ComplexityWe use an extra array.Space ComplexityO(N)Why This Problem is ImportantThis problem teaches:Stable partitioningArray groupingRelative order preservationMulti-pass array processingClean implementation strategyThese concepts are frequently used in:Sorting systemsData pipelinesStream processingPartition-based algorithmsCommon Mistakes1. Using QuickSort Partition LogicQuickSort partitioning does NOT preserve order.This problem specifically requires stable ordering.2. Forgetting Equal ElementsSome solutions only handle:< pivotand> pivotBut pivot values must remain in the center.3. Overcomplicating with Two PointersA simple three-pass solution is cleaner and easier to understand.Interview ExplanationIn interviews explain:Since relative order must remain preserved, we cannot use traditional in-place partitioning. Instead, we perform stable partitioning by collecting smaller, equal, and larger elements sequentially.This demonstrates:Understanding of stable operationsStrong array fundamentalsClean coding approachAlternative ApproachAnother approach is using:Three separate listsThen merging themExample:small + equal + largeBut using one answer array is more space efficient.ConclusionLeetCode 2161 is a simple yet important stable partition problem.The key insight is:We must preserve relative ordering while grouping elements around the pivot.Using a clean three-pass traversal gives an elegant and efficient O(N) solution.

LeetCodeJavaMediumArrayArray PartitionPivot

Quick Sort Algorithm Explained | Java Implementation, Partition Logic & Complexity

IntroductionQuick Sort is one of the most powerful and widely used sorting algorithms in computer science. It follows the Divide and Conquer approach and is known for its excellent average-case performance.What makes Quick Sort special is:It sorts in-place (no extra array required)It is faster in practice than many O(n log n) algorithms like Merge SortIt is heavily used in real-world systems and librariesIn this article, we’ll go deep into:Intuition behind Quick SortPartition logic (most important part)Step-by-step dry runJava implementation with commentsTime complexity analysisCommon mistakes and optimizations🔗 Problem LinkGeeksforGeeks: Quick SortProblem StatementGiven an array arr[], sort it in ascending order using Quick Sort.Requirements:Use Divide and ConquerChoose pivot elementPlace pivot in correct positionElements smaller → left sideElements greater → right sideExamplesExample 1Input:arr = [4, 1, 3, 9, 7]Output:[1, 3, 4, 7, 9]Example 2Input:arr = [2, 1, 6, 10, 4, 1, 3, 9, 7]Output:[1, 1, 2, 3, 4, 6, 7, 9, 10]Core Idea of Quick SortPick a pivot → Place it correctly → Recursively sort left & right🔥 Key Insight (Partition is Everything)Quick Sort depends entirely on partitioning:👉 After partition:Pivot is at its correct sorted positionLeft side → smaller elementsRight side → larger elementsIntuition (Visual Understanding)Consider:[4, 1, 3, 9, 7]Step 1: Choose PivotLet’s say pivot = 4Step 2: Rearrange Elements[1, 3] 4 [9, 7]Now:Left → smallerRight → largerStep 3: Apply RecursivelyLeft: [1, 3]Right: [9, 7]Final result:[1, 3, 4, 7, 9]Partition Logic (Most Important)Your implementation uses:Pivot = first elementTwo pointers:i → moves forwardj → moves backwardJava Codeclass Solution { public void quickSort(int[] arr, int low, int high) { // Base case: if array has 1 or 0 elements if (low < high) { // Partition array and get pivot index int pivotInd = partition(arr, low, high); // Sort left part quickSort(arr, low, pivotInd - 1); // Sort right part quickSort(arr, pivotInd + 1, high); } } // Function to swap two elements void swap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } private int partition(int[] arr, int low, int high) { int pivot = arr[low]; // choosing first element as pivot int i = low + 1; // start from next element int j = high; // start from end while (i <= j) { // Move i forward until element > pivot while (i <= high && arr[i] <= pivot) { i++; } // Move j backward until element <= pivot while (j >= low && arr[j] > pivot) { j--; } // Swap if pointers haven't crossed if (i < j) { swap(arr, i, j); } } // Place pivot at correct position swap(arr, low, j); return j; // return pivot index }}Step-by-Step Dry RunInput:[4, 1, 3, 9, 7]Execution:Pivot = 4i → moves until element > 4j → moves until element ≤ 4Swaps happen → pivot placed correctlyFinal partition:[1, 3, 4, 9, 7]Complexity AnalysisTime ComplexityCaseComplexityBest CaseO(n log n)Average CaseO(n log n)Worst CaseO(n²)Why Worst Case Happens?When array is:Already sortedReverse sortedPivot always becomes smallest/largest.Space ComplexityO(log n) (recursion stack)❌ Common MistakesWrong partition logicInfinite loops in while conditionsIncorrect pivot placementNot handling duplicates properly⚡ Optimizations1. Random PivotAvoid worst-case:int pivotIndex = low + new Random().nextInt(high - low + 1);swap(arr, low, pivotIndex);2. Median of ThreeChoose better pivot:median(arr[low], arr[mid], arr[high])Quick Sort vs Merge SortFeatureQuick SortMerge Sort link to get moreSpaceO(log n)O(n)SpeedFaster (practical)StableWorst CaseO(n²)O(n log n)Why Quick Sort is PreferredCache-friendlyIn-place sortingFaster in real-world scenariosKey TakeawaysPartition is the heart of Quick SortPivot must be placed correctlyRecursion splits problem efficientlyAvoid worst case using random pivotWhen to Use Quick SortLarge arraysMemory constraints (in-place)Performance-critical applicationsConclusionQuick Sort is one of the most efficient and practical sorting algorithms. Mastering its partition logic is crucial for solving advanced problems and performing well in coding interviews.Understanding how pointers move and how pivot is placed will make this algorithm intuitive and powerful.Frequently Asked Questions (FAQs)1. Is Quick Sort stable?No, it is not stable.2. Why is Quick Sort faster than Merge Sort?Because it avoids extra space and is cache-efficient.3. What is the most important part?👉 Partition logic

MediumJavaSortingQuick SortGeeksofGeeks

Search in Rotated Sorted Array – Binary Search Explained with Java Solution (LeetCode 33)

Try the QuestionBefore reading the solution, try solving the problem yourself:👉 https://leetcode.com/problems/search-in-rotated-sorted-array/Attempting the problem first helps build strong algorithmic intuition, which is extremely valuable during coding interviews.Problem StatementYou are given an integer array nums that was originally sorted in ascending order with distinct elements.Example of a sorted array:[0,1,2,4,5,6,7]Before the array is provided to the function, it may have been rotated at some pivot index k.After rotation, the array structure becomes:[nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]For example:Original Array[0,1,2,4,5,6,7]Rotated by 3 positions[4,5,6,7,0,1,2]You are also given an integer target.The goal is to return the index of the target element in the array.If the element does not exist, return:-1Important ConstraintThe algorithm must run in O(log n) time complexity, which strongly suggests using Binary Search.Example WalkthroughExample 1Inputnums = [4,5,6,7,0,1,2]target = 0Output4Explanation:0 exists at index 4Example 2Inputnums = [4,5,6,7,0,1,2]target = 3Output-1Explanation:3 does not exist in the arrayExample 3Inputnums = [1]target = 0Output-1Understanding the Core ChallengeIf the array were fully sorted, the problem would be straightforward because binary search could directly be applied.Example:[1,2,3,4,5,6,7]However, due to rotation:[4,5,6,7,0,1,2]the array is no longer globally sorted.But an important observation makes the problem solvable.Key ObservationEven after rotation:At least one half of the array is always sorted.For example:[4,5,6,7,0,1,2] Left part → sorted Right part → sortedThis property allows the use of binary search with additional conditions.Approach 1 — Linear Scan (Brute Force)The simplest method is to iterate through the entire array and check each element.AlgorithmTraverse the array from start to end.Compare every element with the target.Return the index if found.Codefor(int i = 0; i < nums.length; i++){ if(nums[i] == target){ return i; }}return -1;Time ComplexityO(n)Space ComplexityO(1)Although simple, this solution does not satisfy the required O(log n) complexity.Approach 2 — Modified Binary SearchA better solution uses binary search with sorted half detection.IdeaAt every step:Calculate the middle index.Determine which half of the array is sorted.Check if the target lies inside that sorted half.Adjust the search range accordingly.Implementationpublic int search(int[] nums, int target) { int l = 0; int r = nums.length - 1; while(l <= r){ int mid = l + (r - l) / 2; if(nums[mid] == target){ return mid; } // left half sorted if(nums[l] <= nums[mid]){ if(nums[l] <= target && target < nums[mid]){ r = mid - 1; }else{ l = mid + 1; } } // right half sorted else{ if(nums[mid] < target && target <= nums[r]){ l = mid + 1; }else{ r = mid - 1; } } } return -1;}Time ComplexityO(log n)Space ComplexityO(1)This is the most common interview solution.Approach 3 — Find Rotation Point Then Apply Binary SearchAnother elegant strategy is to first locate the minimum element in the rotated array, which represents the rotation index (pivot).Once the pivot is known, the array can be logically split into two sorted subarrays.Example:[4,5,6,7,0,1,2] ^ pivotTwo sorted sections exist:[4,5,6,7][0,1,2]After identifying the pivot:Decide which part may contain the target.Apply standard binary search on that portion.Step 1 — Finding the Minimum Element (Rotation Pivot)The smallest element indicates where the rotation happened.Function to Find Minimum Valuepublic int findMinIndex(int[] nums){ int l = 0; int r = nums.length - 1; while(l < r){ int mid = l + (r - l) / 2; if(nums[mid] > nums[r]){ l = mid + 1; }else{ r = mid; } } return l;}Why This WorksIf:nums[mid] > nums[r]the minimum element must be on the right side.Otherwise, it lies on the left side (including mid).Step 2 — Standard Binary SearchAfter determining which half contains the target, a normal binary search is applied.public int binarySearch(int[] nums, int l, int r, int target){ while(l <= r){ int mid = l + (r - l) / 2; if(nums[mid] == target){ return mid; } else if(nums[mid] < target){ l = mid + 1; } else{ r = mid - 1; } } return -1;}Complete Solution (Pivot + Binary Search)class Solution { public int findMinIndex(int[] nums){ int l = 0; int r = nums.length - 1; while(l < r){ int mid = l + (r - l) / 2; if(nums[mid] > nums[r]){ l = mid + 1; }else{ r = mid; } } return l; } public int binarySearch(int[] nums, int l, int r, int target){ while(l <= r){ int mid = l + (r - l) / 2; if(nums[mid] == target){ return mid; } else if(nums[mid] < target){ l = mid + 1; } else{ r = mid - 1; } } return -1; } public int search(int[] nums, int target) { int pivot = findMinIndex(nums); if(nums[pivot] <= target && target <= nums[nums.length - 1]){ return binarySearch(nums, pivot, nums.length - 1, target); } return binarySearch(nums, 0, pivot - 1, target); }}Time ComplexityFinding pivot:O(log n)Binary search:O(log n)Total complexity:O(log n)Space ComplexityO(1)No additional memory is used.Key Takeaways✔ The array is sorted but rotated✔ A rotation creates two sorted sections✔ Binary search can still be applied✔ Either detect the sorted half directly or locate the pivot first✔ Both optimized approaches achieve O(log n) complexityFinal ThoughtsThis problem is a classic binary search variation frequently asked in coding interviews. It evaluates the ability to:Recognize structural patterns in arraysAdapt binary search to non-standard conditionsMaintain optimal algorithmic complexityUnderstanding this pattern also helps solve related problems such as:Find Minimum in Rotated Sorted ArraySearch in Rotated Sorted Array IIFind Rotation Count in ArrayMastering these concepts significantly strengthens binary search problem-solving skills for technical interviews.

Binary SearchJavaRotated Sorted ArrayLeetCodeMedium

Find Minimum in Rotated Sorted Array – Binary Search Explained | LeetCode Medium 153

🔗 Try This Problem FirstPlatform: LeetCodeProblem Number: 153👉 Practice here: https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/🧠 Problem UnderstandingYou are given a sorted array that has been rotated between 1 and n times.Example:Original sorted array:[0,1,2,4,5,6,7]After rotation:[4,5,6,7,0,1,2]Your task: 👉 Return the minimum element from this rotated array. 👉 Time complexity must be O(log n). 👉 All elements are unique.🔍 Key ObservationIn a rotated sorted array:The array is divided into two sorted halves.The minimum element is the pivot point where rotation happened.One half will always be sorted.We can use Binary Search to find where the sorted order breaks.Example:[4,5,6,7,0,1,2] ↑ Minimum🚀 Approach 1: Brute Force (Not Allowed by Constraint)IdeaScan entire array and track minimum.int min = nums[0];for(int i = 1; i < nums.length; i++){ min = Math.min(min, nums[i]);}return min;ComplexityTime: O(n)Space: O(1)❌ Not acceptable because problem requires O(log n).🚀 Approach 2: Binary Search (Optimal – O(log n))💡 Core IdeaCompare nums[mid] with nums[right].There are only two possibilities:Case 1: nums[mid] > nums[right]Minimum is in right half.[4,5,6,7,0,1,2]mid rMove left pointer:l = mid + 1Case 2: nums[mid] <= nums[right]Minimum is in left half including mid.[4,5,6,7,0,1,2]mid rMove right pointer:r = mid✅ Optimized Codeclass Solution { public int findMin(int[] nums) { int l = 0; int r = nums.length - 1; while (l < r) { int mid = l + (r - l) / 2; if (nums[mid] > nums[r]) { l = mid + 1; } else { r = mid; } } return nums[r]; }}📊 Dry RunInput:nums = [4,5,6,7,0,1,2]Steplrmidnums[mid]Action106377 > 2 → l = 4246511 <= 2 → r = 5345400 <= 1 → r = 4Stop44--Return nums[4]✅ Output = 0🧩 Why This WorksIf middle element is greater than rightmost, rotation point is to the right.If middle element is smaller than or equal to rightmost, minimum is on the left side.We continuously shrink search space until l == r.That position holds the minimum element.⏱ Time & Space ComplexityMetricValueTime ComplexityO(log n)Space ComplexityO(1)Because:We eliminate half of the array each iteration.No extra space is used.⚠️ Important Edge CasesArray size = 1[10] → 10Already sorted (no visible rotation)[11,13,15,17] → 11Rotation at last position[1,2,3,4,5] → 1🎯 Interview InsightThis problem teaches:Modified Binary SearchIdentifying sorted halvesHandling rotated arraysUnderstanding pivot logicThis is a very common FAANG interview question and often appears in variations like:Search in Rotated Sorted ArrayFind Peak ElementMinimum in Rotated Array with Duplicates🏁 Final TakeawayBrute force works but violates constraint.Binary search is the correct approach.Compare mid with right.Shrink search space until pointers meet.Return nums[l] or nums[r].

LeetcodeMediumBinary Search

LeetCode 154: Find Minimum in Rotated Sorted Array II – Java Binary Search Solution Explained

IntroductionLeetCode 154 – Find Minimum in Rotated Sorted Array II is a classic binary search interview problem.This problem is an advanced version of:Find Minimum in Rotated Sorted ArrayThe major difference is:The array may contain duplicates.That small change makes the problem much harder because duplicates can break normal binary search logic.This problem teaches:Modified binary searchRotated array conceptsHandling duplicatesEdge case optimizationInterview problem-solving techniquesProblem Link🔗 ProblemLeetCode 154: Find Minimum in Rotated Sorted Array IIOfficial Problem: LeetCode Problem LinkProblem StatementAn ascending sorted array is rotated between 1 and n times.Example:[0,1,4,4,5,6,7]may become:[4,5,6,7,0,1,4]or[0,1,4,4,5,6,7]Given the rotated sorted array nums that may contain duplicates, return the minimum element.ExampleExample 1Input:nums = [1,3,5]Output:1Example 2Input:nums = [2,2,2,0,1]Output:0Understanding Rotated Sorted ArraysNormally a sorted array looks like:[1,2,3,4,5]After rotation:[4,5,1,2,3]The minimum element becomes the pivot point.Our goal is to efficiently find this pivot.Brute Force ApproachIntuitionTraverse the entire array and keep track of the smallest element.AlgorithmInitialize minimum as first element.Traverse the array.Update minimum whenever a smaller element appears.Return minimum.Java Code – Brute Forceclass Solution { public int findMin(int[] nums) { int min = nums[0]; for(int num : nums) { min = Math.min(min, num); } return min; }}Dry Run – Brute ForceInput:[2,2,2,0,1]Traversal:ElementMinimum2222220010Final answer:0Complexity Analysis – Brute ForceTime ComplexityO(N)Space ComplexityO(1)Can We Do Better?Yes.Since the array is sorted and rotated, we can use Binary Search.However, duplicates make the problem tricky.Binary Search IntuitionIn a rotated sorted array:One half is always sorted.The minimum lies in the unsorted half.Without duplicates, binary search becomes straightforward.But duplicates create ambiguity.Example:[2,2,2,0,2]If:nums[mid] == nums[right]we cannot determine which side contains the minimum.So we shrink the search space carefully.Key Binary Search ObservationsCase 1If:nums[mid]<nums[right]nums[mid] < nums[right]nums[mid]<nums[right]then the right half is sorted, and minimum may lie at mid or left side.Move:right = midCase 2If:nums[mid]>nums[right]nums[mid] > nums[right]nums[mid]>nums[right]then minimum lies in the right half.Move:left = mid + 1Case 3If:nums[mid]=nums[right]nums[mid] = nums[right]nums[mid]=nums[right]we cannot identify the correct side.Safely reduce search space:right--Optimized Binary Search ApproachStepsInitialize two pointers:leftrightFind middle element.Compare nums[mid] with nums[right].Narrow the search space accordingly.Continue until pointers meet.Java Binary Search Solutionclass Solution { public int findMin(int[] nums) { if(nums.length == 1) return nums[0]; int left = 0; int right = nums.length - 1; int min = Integer.MAX_VALUE; while(left <= right) { int mid = left + (right - left) / 2; if(nums[mid] < nums[right]) { right = mid; min = Math.min(min, nums[right]); } else if(nums[mid] > nums[right]) { min = Math.min(min, nums[right]); left = mid + 1; } else { right--; } min = Math.min(min, nums[mid]); } return min; }}Dry Run – Binary SearchInputnums = [2,2,2,0,1]Initial StateLeftRight04Iteration 1Midmid = 2Value:nums[mid] = 2nums[right] = 1Since:2>12 > 12>1Move:left = mid + 1Now:LeftRight34Iteration 2Midmid = 3Value:nums[mid] = 0nums[right] = 1Since:0<10 < 10<1Move:right = midNow:LeftRight33Final Answer0Time Complexity AnalysisAverage CaseO(log N)Worst CaseDue to duplicates:O(N)Why Worst Case Becomes O(N)Consider:[1,1,1,1,1]Every comparison becomes:nums[mid] == nums[right]We can only shrink by one element:right--This degrades binary search to linear complexity.Interview ExplanationIn interviews, explain:Duplicates destroy the ability to always determine the sorted half uniquely. When nums[mid] == nums[right], we cannot confidently eliminate one side, so we reduce the search space by one element.This is the key insight interviewers look for.Common Mistakes1. Using Standard Binary Search LogicStandard rotated-array logic fails with duplicates.2. Ignoring Duplicate CaseThis condition is essential:else { right--;}3. Infinite Loop ErrorsAlways update pointers carefully.Alternative Simpler Binary SearchA cleaner version:class Solution { public int findMin(int[] nums) { int left = 0; int right = nums.length - 1; while(left < right) { int mid = left + (right - left) / 2; if(nums[mid] < nums[right]) { right = mid; } else if(nums[mid] > nums[right]) { left = mid + 1; } else { right--; } } return nums[left]; }}This is the most common interview solution.FAQsQ1. Why does binary search become O(N)?Duplicates prevent us from discarding half the search space confidently.Q2. Why compare with nums[right]?It helps identify whether the minimum lies on the left or right side.Q3. Is this problem important for interviews?Yes.It is a very popular advanced binary search interview problem.ConclusionLeetCode 154 is an excellent problem for mastering:Modified binary searchRotated sorted arraysDuplicate handlingSearch optimizationThe key challenge is handling:nums[mid]=nums[right]nums[mid] = nums[right]nums[mid]=nums[right]correctly.Once you understand this pattern, many advanced binary search interview problems become much easier.

HardBinary SearchRotated Sorted ArrayJavaLeetCode

Search in Rotated Sorted Array II – Binary Search with Duplicates Explained (LeetCode 81)

Try the QuestionBefore reading the explanation, try solving the problem yourself:👉 https://leetcode.com/problems/search-in-rotated-sorted-array-ii/Practicing the problem first helps develop stronger problem-solving intuition, especially for binary search variations.Problem StatementYou are given an integer array nums that is sorted in non-decreasing order.Example of a sorted array:[0,1,2,4,4,4,5,6,6,7]Before being passed to your function, the array may be rotated at some pivot index k.After rotation, the structure becomes:[nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]Example:Original array[0,1,2,4,4,4,5,6,6,7]Rotated at index 5[4,5,6,6,7,0,1,2,4,4]You are also given an integer target.Your task is to determine:Return true if the target exists in the arrayReturn false if the target does not existThe goal is to minimize the number of operations, which suggests using Binary Search.Example WalkthroughExample 1Inputnums = [2,5,6,0,0,1,2]target = 0OutputtrueExplanation:0 exists in the arrayExample 2Inputnums = [2,5,6,0,0,1,2]target = 3OutputfalseExplanation:3 does not exist in the arrayUnderstanding the Core ChallengeThis problem is very similar to the classic problem:Search in Rotated Sorted Array (LeetCode 33).However, there is an important difference.Difference Between the Two ProblemsProblemArray ValuesRotated Sorted ArrayAll elements are distinctRotated Sorted Array IIArray may contain duplicatesDuplicates introduce ambiguity during binary search.Why Duplicates Make the Problem HarderIn the previous problem, we relied on this rule:If nums[left] <= nums[mid]→ left half is sortedBut duplicates can break this assumption.Example:nums = [1,0,1,1,1]If:left = 0mid = 2right = 4Then:nums[left] = 1nums[mid] = 1nums[right] = 1Here we cannot determine which half is sorted.This is the main complication introduced by duplicates.Key Idea to Handle DuplicatesWhen the values at left, mid, and right are the same, the algorithm cannot decide which half is sorted.To resolve this situation, we shrink the search space:left++right--This gradually removes duplicate values and allows binary search to continue.Modified Binary Search StrategyThe algorithm works as follows:Step 1Calculate the middle index.Step 2If the middle element equals the target:return trueStep 3If duplicates block decision-making:nums[left] == nums[mid] == nums[right]Then move both pointers inward:left++right--Step 4Otherwise, determine which half is sorted and apply normal binary search logic.Java Implementationclass Solution { public boolean search(int[] nums, int target) { int l = 0; int r = nums.length - 1; while (l <= r) { int mid = l + (r - l) / 2; if (nums[mid] == target) return true; // Handle duplicates if (nums[l] == nums[mid] && nums[mid] == nums[r]) { l++; r--; } // Left half sorted else if (nums[l] <= nums[mid]) { if (nums[l] <= target && target < nums[mid]) { r = mid - 1; } else { l = mid + 1; } } // Right half sorted else { if (nums[mid] < target && target <= nums[r]) { l = mid + 1; } else { r = mid - 1; } } } return false; }}Step-by-Step ExampleArray:[2,5,6,0,0,1,2]target = 0Iteration 1mid = 6value = 0Target found immediately.return trueTime ComplexityBest CaseO(log n)When duplicates do not interfere with binary search decisions.Worst CaseO(n)When many duplicate values force the algorithm to shrink the search space one element at a time.Example worst case:[1,1,1,1,1,1,1,1,1]Binary search cannot divide the array effectively.Space ComplexityO(1)The algorithm only uses a few variables and does not require extra memory.Follow-Up: How Do Duplicates Affect Runtime?Without duplicates, binary search always reduces the search space by half.Time Complexity → O(log n)With duplicates, we sometimes cannot determine which half is sorted.In such cases, we shrink the search space linearly:left++right--This may degrade performance to:Worst Case → O(n)However, in most practical cases the algorithm still performs close to logarithmic time.Key Takeaways✔ The array is sorted but rotated✔ Duplicates introduce ambiguity in binary search✔ Special handling is required when nums[left] == nums[mid] == nums[right]✔ The algorithm combines binary search with duplicate handling✔ Worst-case complexity may degrade to O(n)Final ThoughtsThis problem is a natural extension of the rotated sorted array search problem. It tests your ability to adapt binary search to more complex conditions.Understanding this pattern is valuable because similar techniques appear in many interview problems involving:Rotated arraysBinary search edge casesHandling duplicates in sorted data structuresMastering this approach strengthens both algorithmic thinking and interview preparation.

LeetCodeBinary SearchRotated Sorted ArrayJavaMedium