Search A 2D Sorted Matrix - Fundamentals of Search Space Reduction
Back To Back SWE
ยท
Beginner
ยท7y ago
Skills:
Algorithm Basics80%
Free 5-Day Mini-Course: https://backtobackswe.com
Try Our Full Platform: https://backtobackswe.com/pricing
๐น Intuitive Video Explanations
๐ Run Code As You Learn
๐พ Save Progress
โNew Unseen Questions
๐ Get All Solutions
Question: There are 2 versions.
Version 1: Every row is sorted left to right in non-decreasing order. The first integer of each row is greater or equal to the last integer of the previous row.
Version 2: Every row is sorted left to right in non-decreasing order. Every column is sorted top to bottom in non-decreasing order. There are no guarantees that the first item of any row or column relates to the last item in the previous row or column.
Sorted. Binary search is very likely. Investigate, how do we reduce our decision space?
Our first answer does not need to be logarithmic (it is so crucial you understand logarithms and what they mean....you need to know your complexities to refine answers and notice avenues to better solutions).
The key to search problems is that you notice the fundamental decision we can make to reduce the problem.
...more notes I wrote...
++++++++++++++++++++++++++++++++++++++++++++++++++
HackerRank: https://www.youtube.com/channel/UCOf7UPMHBjAavgD0Qw5q5ww
Tuschar Roy: https://www.youtube.com/user/tusharroy2525
GeeksForGeeks: https://www.youtube.com/channel/UC0RhatS1pyxInC00YKjjBqQ
Jarvis Johnson: https://www.youtube.com/user/VSympathyV
Success In Tech: https://www.youtube.com/channel/UC-vYrOAmtrx9sBzJAf3x_xw
Watch on YouTube โ
(saves to browser)
Sign in to unlock AI tutor explanation ยท โก30
Playlist
Uploads from Back To Back SWE ยท Back To Back SWE ยท 57 of 60
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
โถ
58
59
60
4 Tips To Learn Java Programming As Fast As Possible As A Beginner
Back To Back SWE
3 Mistakes Beginners Make When First Learning Java and Android Development
Back To Back SWE
How To Get A Job At Google | The Ultimate Guide To Algorithmic/Coding Interviews
Back To Back SWE
The Ultimate Big O Notation Tutorial (Time & Space Complexity For Algorithms)
Back To Back SWE
Total Occurrences Of K In A Sorted Array (Facebook Software Engineering Interview Question)
Back To Back SWE
The N Queens Problem using Backtracking/Recursion - Explained
Back To Back SWE
Compute All Mnemonics For A Phone Number (Recursion/Backtracking Problem)
Back To Back SWE
How To Reverse A Singly Linked List | The Ultimate Explanation (Iteratively & Recursively)
Back To Back SWE
Depth First & Breadth First Graph Search - DFS & BFS Graph Searching Algorithms
Back To Back SWE
The 0/1 Knapsack Problem (Demystifying Dynamic Programming)
Back To Back SWE
The Dutch National Flag Problem (The Quicksort "Band-Aid")
Back To Back SWE
Test If A Binary Tree Is Symmetric ("Symmetric Tree" on Leetcode)
Back To Back SWE
The IP Address Decomposition Problem - Compute All Valid IP Addresses From Raw IP String
Back To Back SWE
How To Permute A String - Generate All Permutations Of A String
Back To Back SWE
The Balanced Parentheses Problem - Classic Stack Problem ("Valid Parentheses" on Leetcode)
Back To Back SWE
KnuthโMorrisโPratt (KMP) Pattern Matching Substring Search - First Occurrence Of Substring
Back To Back SWE
Implement An LRU Cache - The LRU Cache Eviction Policy ("LRU Cache" on LeetCode)
Back To Back SWE
Find The Longest Increasing Subsequence - Dynamic Programming Fundamentals
Back To Back SWE
Generate All Palindromic Decompositions Of A String ("Palindrome Partitioning" on Leetcode)
Back To Back SWE
Implement A Sudoku Solver - Sudoku Solving Backtracking Algorithm ("Sudoku Solver" on LeetCode)
Back To Back SWE
Merge K Sorted Arrays - Min Heap Algorithm ("Merge K Sorted Lists" on LeetCode)
Back To Back SWE
Partition To K Equal Sum Subsets From An Array of Integers - The Backtracking Approach
Back To Back SWE
Edit Distance Between 2 Strings - The Levenshtein Distance ("Edit Distance" on LeetCode)
Back To Back SWE
Total Ways To Decode A String - Recursive Dynamic Programming Approach ("Decode Ways" on LeetCode)
Back To Back SWE
The Change Making Problem - Fewest Coins To Make Change Dynamic Programming
Back To Back SWE
Compute The Next Permutation of A Numeric Sequence - Case Analysis ("Next Permutation" on Leetcode)
Back To Back SWE
Count Total Unique Binary Search Trees - The nth Catalan Number (Dynamic Programming)
Back To Back SWE
Generate All Strings With n Matched Parentheses - Backtracking ("Generate Parentheses" on LeetCode)
Back To Back SWE
Implement A Max Stack - A Stack With A .max() API (Similar To "Min Stack" on LeetCode)
Back To Back SWE
The Recursive Staircase - Top Down & Bottom Up Dynamic Programming ("Climbing Stairs" on LeetCode)
Back To Back SWE
Search A Maze For Any Path - Depth First Search Fundamentals (Similar To "The Maze" on Leetcode)
Back To Back SWE
Total Unique Ways To Make Change - Dynamic Programming ("Coin Change 2" on LeetCode)
Back To Back SWE
Test If A Binary Tree Is Height Balanced ("Balanced Binary Tree" on LeetCode)
Back To Back SWE
Find The Second Largest Item - Heap & Tracking Approach (Beginner Big N Interview Question)
Back To Back SWE
Increment An Integer Represented As An Array ("Plus One" on LeetCode)
Back To Back SWE
Merge 2 Sorted Lists - A Fundamental Merge Sort Subroutine ("Merge Two Sorted Lists" on LeetCode)
Back To Back SWE
Clone An Undirected Graph - The Utility of Hashtable Mappings ("Clone Graph" on Leetcode)
Back To Back SWE
Clone A Linked List (With Random Pointers) - Linear Space Solution & Tricky Constant Space Solution
Back To Back SWE
Deeply Understanding Logarithms In Time Complexities & Their Role In Computer Science
Back To Back SWE
Implement A Binary Heap - An Efficient Implementation of The Priority Queue ADT (Abstract Data Type)
Back To Back SWE
Max Contiguous Subarray Sum - Cubic Time To Kadane's Algorithm ("Maximum Subarray" on LeetCode)
Back To Back SWE
Binary Tree Bootcamp: Full, Complete, & Perfect Trees. Preorder, Inorder, & Postorder Traversal.
Back To Back SWE
What Is Asymptotic Analysis? And Why Does It Matter? A Deeper Understanding of Asymptotic Notation.
Back To Back SWE
An In-Depth Algorithmic Analysis of Bubble Sort. Best Case, Average Case, & Worst Case.
Back To Back SWE
Maximum Sum Rectangle In A 2D Matrix - Kadane's Algorithm Applications (Dynamic Programming)
Back To Back SWE
A Detailed Algorithmic Analysis of Insertion Sort. Best Case & Worst Case.
Back To Back SWE
Binary Tree Level Order Traversal - Drawing The Parallel Between Trees & Graphs
Back To Back SWE
Implement A Queue Using Stacks - The Queue ADT ("Implement Queue Using Stacks" on LeetCode)
Back To Back SWE
All Nodes Distance K In A Binary Tree - Performing Bidirectional Search On A Tree Using A Hashtable
Back To Back SWE
Longest Common Subsequence (2 Strings) - Dynamic Programming & Competing Subproblems
Back To Back SWE
Egg Dropping Problem: Dynamic Programming Fundamentals & Understanding Subproblem Decomposition
Back To Back SWE
Minimum Window Substring: Utilizing Two Pointers & Tracking Character Mappings With A Hashtable
Back To Back SWE
Reverse Polish Notation: Types of Mathematical Notations & Using A Stack To Solve RPN Expressions
Back To Back SWE
Asymptotic Notations 101: Big O, Big Omega, & Theta (Asymptotic Analysis Bootcamp)
Back To Back SWE
The Backtracking Blueprint: The Legendary 3 Keys To Backtracking Algorithms
Back To Back SWE
Fast Multiplication: From Grade-School Multiplication To Karatsuba's Algorithm
Back To Back SWE
Search A 2D Sorted Matrix - Fundamentals of Search Space Reduction
Back To Back SWE
The Quicksort Sorting Algorithm: Pick A Pivot, Partition, & Recurse
Back To Back SWE
Lowest Common Ancestor Between 2 Binary Tree Nodes (A Recursive Approach)
Back To Back SWE
Sort A K Sorted Array - Investigating Applications of Min/Max Heaps
Back To Back SWE
More on: Algorithm Basics
View skill โ
๐
Tutor Explanation
DeepCamp AI