Binary Search in 2D Matrix

📘 DSA Journey — Day 35 Today’s focus: Binary Search with index patterns. Problem solved: • Single Element in a Sorted Array (LeetCode 540) Concepts used: • Binary Search • Index parity (even/odd pattern) • Search space reduction Key takeaway: The array is sorted and every element appears twice except one. A key observation: Before the single element, pairs start at even indices After the single element, this pattern breaks. Using binary search: • If mid is even and nums[mid] == nums[mid + 1], the single element lies on the right side • Else, it lies on the left side (including mid) By leveraging this pattern, we can find the answer in O(log n) time and O(1) space. Continuing to strengthen binary search intuition and consistency in problem solving. #DSA #Java #LeetCode #CodingJourney

Today's problem was HARD. But the pattern was familiar. Binary Search on Answer... again. 🚀 Day 92/365 — DSA Challenge Solved: Find K-th Smallest Pair Distance Problem: Find the k-th smallest distance among all pairs. Brute force: Generate all pairs → O(n²) → Too slow. Better idea: Binary search the distance. For a distance d: Count how many pairs have distance ≤ d. If count ≥ k → try smaller distance Else → increase distance The interesting part: We count pairs using Sliding Window in O(n). So the final solution becomes: Binary Search + Sliding Window. ⏱ Time: O(n log range) 📦 Space: O(1) Day 92/365 complete. 💻 273 days to go. Code: https://lnkd.in/dad5sZfu #DSA #Java #LeetCode #BinarySearch #SlidingWindow #Algorithms #LearningInPublic

🚀 Day 44/60 – DSA Challenge Today’s problem was about finding the minimum element in a rotated sorted array using Binary Search 🔍 🔍 Problem Solved: Given a sorted array that has been rotated, find the minimum element efficiently. 🧠 Approach I Used: Instead of scanning the array linearly, I used Binary Search: Compare the middle element with the last element If the middle is greater → minimum lies on the right side Otherwise → minimum lies on the left side Keep shrinking the search space until the answer is found ⚡ Key Insight: The comparison with the last element helps determine which part of the array is sorted and where the minimum lies. 📈 Complexity: Time: O(log n) Space: O(1) 🎯 What I Learned: Binary Search can be adapted to solve rotated array problems Understanding array structure is more important than memorizing logic Edge cases and boundary handling are crucial for correctness Improving step by step, one problem at a time 🔥 #Day44 #DSAChallenge #BinarySearch #Java #ProblemSolving #Consistency

Day 61/75 — Two Sum II (Input Array Is Sorted) Today’s problem was about finding two numbers in a sorted array that add up to a target. Approach: • Use two-pointer technique (left & right) • If sum > target → move right pointer left • If sum < target → move left pointer right • Stop when sum equals target Key logic: while (i < j) { int sum = numbers[i] + numbers[j]; if (sum == target) return new int[]{i + 1, j + 1}; else if (sum > target) j--; else i++; } Time Complexity: O(n) Space Complexity: O(1) A classic two-pointer problem that reinforces working with sorted arrays efficiently. 61/75 🚀 #Day61 #DSA #TwoPointers #Arrays #Java #Algorithms #LeetCode

Day 8/30 — DSA Challenge 🚀 Problem: Search a 2D Matrix II Topic: Matrix + Binary Search Pattern Difficulty: Medium Approach: Started from top-right corner of the matrix If current element == target → return true If current element < target → move down If current element > target → move left Mistake / Challenge: Initially tried applying binary search like previous problem (LeetCode 74) Realized matrix is not globally sorted, so that approach fails Fix: Used optimal “staircase search” approach Reduced time complexity efficiently Key Learning: Not all sorted matrices can be treated as 1D arrays Recognize pattern: row-wise + column-wise sorted → use pointer approach Time Taken: 45 minutes Consistency check ✅ See you on Day 9. GitHub Repo: https://lnkd.in/gHW9vKUf #DSA #LeetCode #Java #Matrix #BinarySearch #LearningInPublic

Day 7/30 — DSA Challenge 🚀 Problem: Search a 2D Matrix Topic: Binary Search Difficulty: Medium Approach: Treated the 2D matrix as a flattened sorted array Applied Binary Search from 0 to (m * n - 1) Converted index → row = mid / m, col = mid % m Mistake / Challenge: Initially thought of searching row by row (O(n + m)) Realized problem expects O(log(m*n)) Fix: Applied Binary Search on the entire matrix Used index mapping to access elements Key Learning: Whenever matrix is sorted like this → think “1D Binary Search” Index mapping trick (row, col) is very powerful Time Taken: 40 minutes Consistency check ✅ See you on Day 8. GitHub Repo: https://lnkd.in/gHW9vKUf #DSA #LeetCode #Java #BinarySearch #Matrix #LearningInPublic

📘 DSA Journey — Day 26 Today’s focus: Binary Search fundamentals. Problems solved: • Binary Search (LeetCode 704) • Search a 2D Matrix (LeetCode 74) Concepts used: • Binary Search • Search space reduction • Index mapping in 2D arrays Key takeaway: In Binary Search, the idea is to repeatedly divide the search space in half. By comparing the target with the middle element, we eliminate half of the array each time, achieving O(log n) time complexity. In Search a 2D Matrix, the matrix can be treated as a flattened sorted array. Using index mapping: row = mid / cols col = mid % cols we can apply binary search directly on the matrix without extra space. These problems highlight how binary search is not limited to 1D arrays—it can be extended to structured data with proper transformations. Continuing to strengthen fundamentals and consistency in DSA problem solving. #DSA #Java #LeetCode #CodingJourney

Day 82/90 Solved: Sliding Window Maximum Basic idea: Brute force → check max in every window → O(n·k) (useless for large input) Optimized logic: → Use a monotonic decreasing deque → Store indices, not values → Front = current window max → Remove: Out-of-window indices (from front) Smaller elements (from back) Result: Every element is pushed & popped once → O(n) Real learning: The problem is not sliding window — it’s maintaining max in O(1) using the right data structure. #Consistency #DSA #LeetCode #SlidingWindow #Deque #MonotonicQueue #Java #Algorithms

Day 49/75 — Rearrange Array Elements by Sign Today’s problem focused on rearranging an array such that positive and negative numbers alternate, while preserving their original order. Approach: • Use two pointers (even index for positive, odd index for negative) • Traverse the array once • Place elements in correct positions directly Key logic: if (num >= 0) { result[posIdx] = num; posIdx += 2; } else { result[negIdx] = num; negIdx += 2; } Time Complexity: O(n) Space Complexity: O(n) A clean problem that reinforces index placement and pattern-based traversal. 49/75 🚀 #Day49 #DSA #Arrays #Java #Algorithms #LeetCode

Day 60 – Search a 2D Matrix Solved a problem to efficiently search for a target in a sorted matrix using binary search. Key Learnings: Learned to treat a 2D matrix as a flattened sorted array Understood index mapping from 1D to 2D (row = mid / cols, col = mid % cols) Strengthened problem-solving skills in optimized searching techniques #DSA #Java #BinarySearch #Matrix #ProblemSolving #CodingPractice