Source: Data Structures and Algorithms MCQ & Short Answer Review
Tags: SLMP, sorted list match, common elements, sorted arrays, brute force, two-pointer technique, nested loops, O(n²), O(n), time complexity comparison, C functions, algorithm optimisation
Difficulty: Beginner to Intermediate Prerequisites: Comfortable with linear search, basic loop constructs in C, and Big-O notation. The searching algorithms study notes for this unit cover the prerequisite material.
The Sorted List Match Problem (SLMP) asks you to find all common elements between two sorted arrays. It is a classic teaching problem because it can be solved at several levels of efficiency, from a naive O(n²) brute-force approach down to an elegant O(n) two-pointer scan. Walking through the versions teaches you how to exploit structure in your input (here, the fact that both arrays are sorted) to eliminate unnecessary work. This progression from brute force to optimal solution is a pattern you will see repeatedly in algorithm design.
SLMP finds common elements in two sorted arrays. Version 1 uses nested loops and runs in O(n²). Version 2 reduces comparisons but is still suboptimal. Version 3 uses a two-pointer technique and runs in O(n), making it the best of the three.
SLMP (Sorted List Match Problem)
The problem of finding and printing all elements that appear in both of two sorted arrays. In simple terms, you have two sorted lists and you want to know which values they share.
Brute-force approach (Version 1)
A solution that uses nested loops to compare every element of array A with every element of array B. It is correct but slow: O(n²) in the worst case, because each of the n elements in A is compared against up to m elements in B.
Two-pointer technique (Version 3)
A strategy that maintains one pointer (index) per array and advances the pointer that points to the smaller value. When both pointers point to equal values, a match is found. Because each pointer only moves forward, the total work is O(n + m), which simplifies to O(n) when the arrays are roughly the same size.
Contiguous subarray
A sequence of consecutive elements within an array. Some formulations of "SLMP" in other courses refer to the Maximum Subarray Problem (finding the contiguous subarray with the largest sum). The source material here uses SLMP primarily for sorted-list matching, but be aware of this alternate usage.
For each element in A, scan the entirety of B looking for a match. The early-exit optimisation (break when B[j] > A[i]) helps in practice but does not change the worst-case complexity.
void slmp_bruteForce(int A[], int n, int B[], int m) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (A[i] == B[j]) {
printf("%d ", A[i]);
break; // avoid printing duplicates
} else if (B[j] > A[i]) {
break; // early exit since B is sorted
}
}
}
}
Time complexity: O(n × m), commonly written O(n²) when n ≈ m
Uses nested loops
The break on B[j] > A[i] is a useful optimisation that exploits the sorted order of B, but the outer loop still restarts the inner loop from j = 0 each time
Version 2 improves over Version 1 by reducing the number of comparisons. The source material does not provide the full implementation, but the key insight is that once you know where you stopped in B for the previous element of A, you do not need to restart B from the beginning. This avoids redundant comparisons but still falls short of optimal.
Both pointers start at index 0. At each step, compare the current elements. If they match, print and advance both. If A's element is smaller, advance A's pointer. If B's element is smaller, advance B's pointer. Each pointer moves at most n or m steps total, so the combined work is O(n + m).
void sortedListMatch(int A[], int n, int B[], int m) {
int i = 0, j = 0;
while (i < n && j < m) {
if (A[i] == B[j]) {
printf("%d ", A[i]);
i++;
j++;
} else if (A[i] < B[j]) {
i++;
} else {
j++;
}
}
}
Time complexity: O(n + m), which is O(n) when both arrays are similar in size
Each element is visited at most once
No nested loops
A = {1, 3, 4, 5, 7}, B = {2, 3, 5, 6}
Compare 1 and 2: 1 < 2, advance i
Compare 3 and 2: 3 > 2, advance j
Compare 3 and 3: match, print 3, advance both
Compare 4 and 5: 4 < 5, advance i
Compare 5 and 5: match, print 5, advance both
Compare 7 and 6: 7 > 6, advance j
j reaches end of B, loop terminates
Output: 3 5
Version | Strategy | Time Complexity |
|---|---|---|
Version 1 | Nested loops (brute force) | O(n²) |
Version 2 | Reduced comparisons | Between O(n²) and O(n) |
Version 3 | Two-pointer scan | O(n) |
The jump from Version 1 to Version 3 is significant. For two arrays of 10,000 elements each, Version 1 may perform up to 100,000,000 comparisons. Version 3 performs at most 20,000.
Finding common elements between sorted lists is a fundamental operation in database joins (particularly merge joins on indexed columns), search engine result intersection (combining results from multiple query terms), and version control systems that compare sorted lists of file changes. The two-pointer technique generalises to any problem where you are merging or comparing two sorted sequences.
Students sometimes assume all three SLMP versions produce different output. They do not. All three produce the same correct result; only the efficiency differs.
The early break in Version 1 (when B[j] > A[i]) is sometimes mistaken for making the algorithm O(n). It reduces average-case work but the worst case remains O(n²) because the inner loop restarts from 0 for each element of A.
Students occasionally confuse the SLMP (sorted list matching) with the Maximum Subarray Problem (also sometimes abbreviated SLMP or referred to as Kadane's algorithm). The source material uses SLMP for both contexts. If an exam question mentions "maximum sum of a contiguous subarray," that is the subarray problem, not the list-matching problem.
In the two-pointer version, students sometimes advance only one pointer on a match. Both must advance, otherwise you will print duplicates or loop forever.
⚠️ Know the time complexity of each version. Version 1 is O(n²), Version 3 is O(n). This is a direct exam question.
⚠️ Be able to trace Version 3 by hand. Show the state of i and j at each step and the output produced.
⚠️ Expect a question asking you to compare Versions 1 and 3 and explain why Version 3 is more efficient. The answer is that Version 3 never revisits an element.
⚠️ Version 1 uses nested loops, Version 3 does not. If asked "which version uses nested loops," the answer is Version 1.
True or false: SLMP Version 3 has the best time complexity of the three versions. Answer: True.
Fill in the blank: SLMP Version 2 improves over Version 1 by reducing the number of ______. Answer: Comparisons.
True or false: SLMP Version 1 uses divide and conquer. Answer: False. It uses nested loops.
Fill in the blank: the time complexity of SLMP Version 1 is ______. Answer: O(n²).
True or false: in the two-pointer technique, you advance both pointers when a match is found. Answer: True.
Q: What is the purpose of SLMP?
A: To find all common elements between two sorted arrays (or, in some formulations, to find the maximum sum of a contiguous subarray in a given array).
Q: Compare the runtime of SLMP Version 1 and Version 3.
A: Version 1 runs in O(n²) due to nested loops. Version 3 runs in O(n) using the two-pointer technique. Version 3 is significantly more efficient because each element in both arrays is visited at most once.
Q: In the brute-force SLMP (Version 1), why does the inner loop break when B[j] > A[i]?
A: Because B is sorted. Once an element in B exceeds the current element of A, no later element in B can equal A[i] either, so continuing the inner loop would be wasted work.
Q: Trace sortedListMatch(A, 5, B, 4) where A = {1, 3, 4, 5, 7} and B = {2, 3, 5, 6}.
A: The pointers walk through both arrays, printing 3 (when both point to 3) and 5 (when both point to 5). Output: 3 5.
Q: Why does Version 3 not need nested loops?
A: Because both arrays are sorted, a single pass with two pointers is sufficient. The smaller-element pointer advances until it catches up, so no element needs to be revisited. This eliminates the need for an inner loop that restarts from the beginning.
The two-pointer technique reappears in merge sort's merge step, where two sorted halves are combined into one sorted array using the same pointer-advancement logic. It also connects to the broader theme of exploiting sorted data, which you will encounter again with binary search trees, heaps, and hash-based set intersection (an alternative O(n) approach that does not require sorted input). The progression from brute force to optimal is the same design pattern you will follow when studying dynamic programming later in the course.
sorted list match, SLMP, common elements sorted arrays, two-pointer technique, merge step, brute force nested loops, O(n²) to O(n) optimisation, array intersection, merge join, sorted array comparison, Kadane's algorithm, maximum subarray, contiguous subarray sum, DSA 101, Computer Science I, UCF