Longest common block
Given two lists of integers nums1 and nums2, return the length of the longest
contiguous block of values that appears in both. (For strings this is the longest common substring.)
Examples
| Input | Output | Why |
|---|---|---|
nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7] | 3 | The block 3, 2, 1. |
nums1 = [0,0,0,0,0], nums2 = [0,0,0,0,0] | 5 | The whole list. |
nums1 = [1,2], nums2 = [3,4] | 0 | No common value. |
Constraints
- 1 ≤ nums1.length, nums2.length ≤ 1000
- 0 ≤ nums[i] ≤ 100
Hints
Hint 1
Unlike a subsequence, a block that is interrupted cannot continue. Fix where the block ends.
Hint 2
E[i][j] = length of the longest common block ending exactly at nums1[i − 1] and nums2[j − 1].
Hint 3
E[i][j] = E[i − 1][j − 1] + 1 on a match, else 0. The answer is the largest E anywhere.
Where people lose marks
- Using the subsequence recurrence (max of above and left on a mismatch), which allows gaps.
- Reading the answer from the bottom-right corner instead of taking the maximum entry.
- Updating a single row left to right in place, which overwrites the diagonal value still needed (go right to left, or keep two rows).
Dry run on [1,2,3,2,1],[3,2,1,4,7]
Read it one frame at a time, the way you would trace the code on paper in an interview. Each frame shows the state after the step it describes.
-
Step 1 / 6
Base cases filled first.
-
Step 2 / 6
1 ≠ 3: no block ends here, 0. 1 ≠ 2: no block ends here, 0. 1 = 1: extend the diagonal to 1. 1 ≠ 4: no block ends here, 0. 1 ≠ 7: no block ends here, 0.
-
Step 3 / 6
2 ≠ 3: no block ends here, 0. 2 = 2: extend the diagonal to 1. 2 ≠ 1: no block ends here, 0. 2 ≠ 4: no block ends here, 0. 2 ≠ 7: no block ends here, 0.
-
Step 4 / 6
3 = 3: extend the diagonal to 1. 3 ≠ 2: no block ends here, 0. 3 ≠ 1: no block ends here, 0. 3 ≠ 4: no block ends here, 0. 3 ≠ 7: no block ends here, 0.
-
Step 5 / 6
2 ≠ 3: no block ends here, 0. 2 = 2: extend the diagonal to 2. 2 ≠ 1: no block ends here, 0. 2 ≠ 4: no block ends here, 0. 2 ≠ 7: no block ends here, 0.
-
Step 6 / 6
1 ≠ 3: no block ends here, 0. 1 ≠ 2: no block ends here, 0. 1 = 1: extend the diagonal to 3. 1 ≠ 4: no block ends here, 0. 1 ≠ 7: no block ends here, 0. The largest entry is 3.
How to think about it
Let E[i][j] be the length of the longest common block that ends exactly at nums1[i − 1] and
nums2[j − 1]. If those values are equal, the block extends the one ending one step earlier in both:
E[i][j] = E[i − 1][j − 1] + 1. If they differ, no common block ends there, so E[i][j] = 0. The
answer is the maximum entry. Each row depends only on the previous one, so two rows of length m suffice.
Complexity. Time O(n · m) · Space O(m)
The solution, in six languages
Each one is compiled and run against the test table before it is published. Java is reviewed by hand.
def longest_common_block(nums1, nums2):
m = len(nums2)
prev = [0] * (m + 1) # E for the previous row
best = 0
for x in nums1:
cur = [0] * (m + 1)
for j in range(1, m + 1):
if x == nums2[j - 1]:
cur[j] = prev[j - 1] + 1 # extend the block ending one step earlier
best = max(best, cur[j])
prev = cur
return best#include <algorithm>
#include <vector>
int solve(const std::vector<int>& nums1, const std::vector<int>& nums2) {
const int m = nums2.size();
std::vector<int> prev(m + 1, 0), cur(m + 1, 0);
int best = 0;
for (int x : nums1) {
for (int j = 1; j <= m; ++j) {
cur[j] = x == nums2[j - 1] ? prev[j - 1] + 1 : 0;
best = std::max(best, cur[j]);
}
std::swap(prev, cur);
}
return best;
}class Solution {
public int longestCommonBlock(int[] nums1, int[] nums2) {
int m = nums2.length, best = 0;
int[] prev = new int[m + 1], cur = new int[m + 1];
for (int x : nums1) {
for (int j = 1; j <= m; j++) {
cur[j] = x == nums2[j - 1] ? prev[j - 1] + 1 : 0;
best = Math.max(best, cur[j]);
}
int[] t = prev; prev = cur; cur = t;
}
return best;
}
}function longestCommonBlock(nums1, nums2) {
const m = nums2.length;
let prev = new Array(m + 1).fill(0), best = 0;
for (const x of nums1) {
const cur = new Array(m + 1).fill(0);
for (let j = 1; j <= m; j++) if (x === nums2[j - 1]) { cur[j] = prev[j - 1] + 1; best = Math.max(best, cur[j]); }
prev = cur;
}
return best;
}fn solve(nums1: &[i64], nums2: &[i64]) -> i64 {
let m = nums2.len();
let mut prev = vec![0i64; m + 1];
let mut best = 0;
for &x in nums1 {
let mut cur = vec![0i64; m + 1];
for j in 1..=m {
if x == nums2[j - 1] {
cur[j] = prev[j - 1] + 1;
best = best.max(cur[j]);
}
}
prev = cur;
}
best
}solve :: [Int] -> [Int] -> Int
solve a b = maximum (0 : concat rows)
where
-- each row: E for one element of the first list against every element of the second
rows = tail (scanl row (replicate (length b) 0) a)
row prev x = zipWith3 (\y diag _ -> if x == y then diag + 1 else 0) b (0 : prev) prevVariants to try
- Return the block itself (remember where the maximum occurred).
- For long strings, binary search on the length with rolling hashes: O((n + m) log(min(n, m))).
- The longest block that appears at least twice within one string (a suffix array, or this DP on the string with itself, excluding the diagonal).
Next problems
The cheapest way up a staircase
Each step has a cost; climb one or two steps at a time; start on step 0 or 1. Return the cheapest way past the top.
Open the problem → Medium15 minCan a subset reach the target?
Decide whether some subset of positive integers adds up to exactly the target. A boolean array over totals, filled downwards for each number.
Open the problem → Medium15 minCount the palindromic substrings
Count every contiguous substring that reads the same backwards, counting different positions separately. Each successful expansion step is one more.
Open the problem →Write a solution and run it against the real test table.
Keep going
The cheapest way up a staircase
Each step has a cost; climb one or two steps at a time; start on step 0 or 1. Return the cheapest way past the top.
Open the problem → Medium15 minCan a subset reach the target?
Decide whether some subset of positive integers adds up to exactly the target. A boolean array over totals, filled downwards for each number.
Open the problem → Medium15 minCount the palindromic substrings
Count every contiguous substring that reads the same backwards, counting different positions separately. Each successful expansion step is one more.
Open the problem → Dynamic programmingThe pattern behind it
Write the recursion, notice the repeats, fill a table in an order that makes each entry final.
Read the pattern →Preparing for a real process? Quant interview preparation, or book a free 20-minute call.