Binary Search in Rotated Sorted Array with Java

#CodeEveryday — My DSA Journey | Day 2 🧩 Problem Solved: Combination Sum II (LeetCode) 💭 What I Learned: Used backtracking to generate all unique combinations whose sum equals the target. Sorted the array initially to efficiently handle duplicates and enable pruning. At each step: ✔️ Skipped duplicate elements using i > n && nums[i] == nums[i-1] ✔️ Stopped recursion early when the current element exceeded the target ✔️ Moved to the next index (i+1) to avoid reusing elements Strengthened my understanding of handling duplicates in recursion and optimizing search space. ⏱ Time Complexity: O(2ⁿ)*k (k is avg length of each combination) 🧠 Space Complexity: O(n) ⚡ Key Takeaways: ✔️ Sorting helps in both pruning and duplicate handling ✔️ Skipping duplicates is crucial for unique combinations ✔️ Backtracking becomes efficient with early stopping conditions 💻 Language Used: Java ☕ 📘 Concepts: Backtracking · Recursion · Arrays · Duplicate Handling · Pruning #CodeEveryday #DSA #LeetCode #Java #Backtracking #ProblemSolving #Algorithms #CodingJourney #Consistency 🚀

📘 DSA Journey — Day 31 Today’s focus: Binary Search for boundaries and square roots. Problems solved: • Sqrt(x) (LeetCode 69) • Search Insert Position (LeetCode 35) Concepts used: • Binary Search • Search space reduction • Boundary conditions Key takeaway: In Sqrt(x), the goal is to find the integer square root. Using binary search, we search in the range [1, x] and check mid * mid against x to narrow down the answer. This avoids linear iteration and achieves O(log n) time. In Search Insert Position, we use binary search to find either: • The exact position of the target, or • The correct index where it should be inserted The key idea is that when the target is not found, the final position of the left pointer gives the correct insertion index. These problems highlight how binary search is not just for finding elements, but also for determining positions and boundaries efficiently. Continuing to strengthen fundamentals and consistency in problem solving. #DSA #Java #LeetCode #CodingJourney

📘 DSA Journey — Day 29 Today’s focus: Binary Search on answer space. Problem solved: • Find Peak Element (LeetCode 162) Concepts used: • Binary Search • Observing slope / trend • Search space reduction Key takeaway: The goal is to find a peak element (an element greater than its neighbors). Instead of checking all elements, we use binary search by observing the slope: • If nums[mid] < nums[mid + 1] → we are on an increasing slope, so a peak must exist on the right side • Else → we are on a decreasing slope, so a peak lies on the left side (including mid) By following this logic, we eliminate half of the search space each time and find a peak in O(log n) time. The key insight is: A peak is guaranteed to exist, and the direction of slope helps guide the search. Continuing to strengthen binary search intuition and consistency in problem solving. #DSA #Java #LeetCode #CodingJourney

LeetCode — Problem 33 | Day 17 💡 Problem: Search in Rotated Sorted Array --- Given a rotated sorted array nums and a target, return the index of target if found, otherwise return -1. --- 🧠Approach (Modified Binary Search): - Use Binary Search (low, high, mid) - At every step, one half is always sorted - If left half is sorted: check if target lies between nums[low] and nums[mid] - Else right half is sorted: check if target lies between nums[mid] and nums[high] - Narrow down the search space accordingly --- Key Idea: Even after rotation, one half of the array is always sorted → use this to eliminate half search space --- Time Complexity: O(log n) Space Complexity: O(1) --- Key Learning: - Binary search can be modified for rotated arrays - Identifying sorted half is the main trick - Efficient searching by reducing space every step --- #LeetCode #DSA #Java #BinarySearch #CodingJourney #InterviewPrep

📘 DSA Journey — Day 33 Today’s focus: Binary Search for next greater element. Problem solved: • Find Smallest Letter Greater Than Target (LeetCode 744) Concepts used: • Binary Search • Upper bound concept • Circular handling Key takeaway: The goal is to find the smallest character strictly greater than a given target in a sorted array. This is a classic upper bound problem: We use binary search to find the first element greater than the target. During search: • If letters[mid] > target, store it as a possible answer and move left • Else move right An important edge case: If no character is greater than the target, we return the first element (circular behavior). Continuing to strengthen binary search patterns and problem-solving consistency. #DSA #Java #LeetCode #CodingJourney

Beginning this journey to learn in public and stay consistent with Problem :- Contains Duplicate (LeetCode 217) Problem Statement :- Given an integer array, return true if any value appears at least twice, otherwise return false. Approach 1 :- Brute Force (Nested Loops) i - Compare every element with others ii - Time Complexity:- O(n²) => because of nested loops iii - Simple but inefficient for large inputs class Solution {    public boolean containsDuplicate(int[] nums) {      for (int i = 0; i < nums.length - 1; i++) {        for (int j = i + 1; j < nums.length; j++) {          if (nums[i] == nums[j])            return true;        }      }      return false;    } } Approach 2 :- Optimized (Sorting) Sort array → check adjacent elements Time Complexity:- O(n log n) class Solution {    public boolean containsDuplicate(int[] nums) {      Arrays.sort(nums);     for (int i = 1; i < nums.length; i++) {        if (nums[i] == nums[i - 1])          return true;      }     return false;    } } Key Learning: Start with brute force → then optimize. How would you optimize this further? One problem. Every day. No shortcuts, just consistency. #LeetCode #Java #DSA #CodingChallenge #SoftwareEngineering #Arrays #Sorting

📘 DSA Journey — Day 36 Today’s focus: Binary Search for boundaries. Problem solved: • Find First and Last Position of Element in Sorted Array (LeetCode 34) Concepts used: • Binary Search • Lower bound & upper bound • Searching boundaries efficiently Key takeaway: The goal is to find the first and last occurrence of a target in a sorted array. Instead of scanning linearly, we perform two binary searches: • First search → find the leftmost (first) occurrence • Second search → find the rightmost (last) occurrence Key idea: When we find the target: • For left boundary → continue searching in the left half • For right boundary → continue searching in the right half This ensures we capture the full range in O(log n) time. Continuing to strengthen binary search patterns and problem-solving consistency. #DSA #Java #LeetCode #CodingJourney

🚀 From Brute Force to Optimization — Pair Sum Problem While learning DSA, I explored how a simple problem can be optimized with the right approach. 💡 Problem: Find if any pair in a sorted array has a target sum. 💡 Brute Force: • Check every possible pair • Time Complexity: O(n²) ⚡ Optimization Insight: O(n²) → O(n) 💡 Optimized Approach (Two Pointer): • Start with two pointers at left and right ends • If sum == target → found • If sum < target → move left pointer forward • If sum > target → move right pointer backward • Time Complexity: O(n) This problem helped me understand how choosing the right approach can drastically improve performance. Excited to keep improving problem-solving skills one step at a time 🚀 #DSA #Java #TwoPointer #ProblemSolving #LearningJourney

----Continuing my DSA journey---- * Problem: Parse Lisp Expression (736) * Approach: I solved this using recursion + hashmap (scope handling). I parsed the expression and evaluated it based on three cases: • add → evaluate both expressions and sum • mult → evaluate both expressions and multiply • let → assign variables and evaluate in scoped context I used a HashMap to maintain variable values and passed copies to handle nested scopes correctly. * Key Insight: The tricky part was managing variable scope in nested expressions. Each "let" creates a new scope, and variables must be resolved from inner to outer scope. * What I Learned: This problem improved my understanding of parsing complex expressions and scope management. #LeetCode #DSA #Java #Recursion #HashMap #ProblemSolving

🚀 DAY 99/150 — BINARY SEARCH ON ANSWER! 🔥📊 Day 99 of my 150 Days DSA Challenge in Java and today I solved a very important problem that uses Binary Search in a 2D matrix 💻🧠 📌 Problem Solved: Kth Smallest Element in a Sorted Matrix 📌 LeetCode: #378 📌 Difficulty: Medium–Hard 🔹 Problem Insight The task is to find the kth smallest element in an n x n matrix where: • Each row is sorted • Each column is sorted 👉 Instead of flattening and sorting (O(n² log n)), we can do better using Binary Search on Answer. 🔹 Approach Used I used Binary Search on Value Range: • Set: low = smallest element high = largest element • Apply binary search: Find mid Count how many elements are ≤ mid 👉 If count < k → move right (low = mid + 1) 👉 Else → move left (high = mid) ✔️ Continue until low == high → answer found 🔹 Counting Logic (Optimized) • Start from bottom-left corner • If element ≤ mid: All elements above are also ≤ mid Move right • Else: Move up ✔️ This gives O(n) counting per iteration ⏱ Complexity Time Complexity: O(n log (max - min)) Space Complexity: O(1) 🧠 What I Learned • Binary Search is not just for arrays — it can be applied on answer space • Matrix properties can be used for efficient counting • Avoid brute force by leveraging sorted structure 💡 Key Takeaway This problem taught me: How to apply Binary Search on Answer pattern How to optimize 2D problems using structure Thinking beyond direct sorting approaches 🌱 Learning Insight Now I’m improving at: 👉 Recognizing when to use Binary Search beyond arrays 👉 Solving problems with optimized thinking 🚀 ✅ Day 99 completed 🚀 51 days to go 🔗 Java Solution on GitHub: 👉 https://lnkd.in/g-yhc7kH 💡 Don’t search the data — search the answer. #DSAChallenge #Java #LeetCode #BinarySearch #Matrix #Optimization #150DaysOfCode #ProblemSolving #CodingJourney #InterviewPrep #LearningInPublic