Find Smallest Common Row Value
Company: SoFi
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Technical Screen
You are given a 2D integer matrix where each row is sorted in strictly increasing order. Return the smallest integer that appears in every row. If no such integer exists, return -1.
Assumptions:
- The matrix contains at least 1 row and 1 column.
- All rows have the same length.
- Values can be negative or positive.
Example:
Input:
[
[1, 2, 3, 4, 5],
[2, 4, 5, 8, 10],
[3, 5, 7, 9, 11],
[1, 3, 5, 7, 9]
]
Output:
5
During the interview, you may also be asked to clarify edge cases and write test methods or unit test cases for your solution.
Quick Answer: This question evaluates algorithmic problem-solving skills focused on array processing, intersection across multiple sorted sequences, and time/space complexity analysis.
You are given a 2D integer matrix where each row is sorted in strictly increasing order. Return the smallest integer that appears in every row. If no such integer exists, return -1.
Because each row is sorted, you should aim for a solution that uses that structure instead of comparing every value against every other value blindly.
Constraints
- 1 <= number of rows <= 1000
- 1 <= number of columns <= 1000
- All rows have the same length
- Each row is sorted in strictly increasing order
- -10^9 <= matrix[i][j] <= 10^9
Examples
Input: ([[1,2,3,4,5],[2,4,5,8,10],[3,5,7,9,11],[1,3,5,7,9]],)
Expected Output: 5
Explanation: The value 5 appears in every row, and no smaller value does.
Input: ([[-4,-1,0,9]],)
Expected Output: -4
Explanation: With only one row, every value in that row appears in every row. The smallest is -4.
Hints
- Any valid answer must come from the first row, so you can test its values from left to right.
- Since every row is sorted, use binary search to check whether a candidate appears in the other rows.