These are the notes for C Coding Questions, episode 11, placement practice for people who finished the SyntaxPilot C course. Array questions, part five (the last array episode): merging two sorted arrays with two pointers, the union and intersection of two sorted arrays without duplicates, and the maximum subarray sum with Kadane's algorithm (and the all-negative case that breaks the common version).
Each question follows the same steps: read the problem, think out loud, the obvious attempt, a real failure, why, the fix, every test case, and the complexity.
Every program was compiled with gcc -Wall -O2 -Wno-unused-result main.c -o main -lm (gcc 13.3, Linux x86-64, 32-bit int), the SyntaxPilot compiler's C command with warnings on, and every output below is real. The compiler stops a program after 8 seconds (Time Limit Exceeded), like an online judge.
Real-life pictures
| In real life | In C |
|---|---|
| two class lists, each sorted by roll number, become one sorted school list | merge two sorted arrays |
| students in the chess club or the music club; students in both | union and intersection, each value once |
| a shopkeeper's diary of daily profit and loss: the best run of consecutive days | maximum subarray sum |
Q1: Merge two sorted arrays
Problem. Read n, then n sorted integers, then m, then m sorted integers. Print all n + m values in sorted order.
| Input | Output |
|---|---|
3 / 1 3 5 / 5 / 2 4 6 8 10 |
1 2 3 4 5 6 8 10 |
3 / 4 5 6 / 0 |
4 5 6 |
3 / -2 2 2 / 3 / -5 2 9 |
-5 -2 2 2 2 9 |
Edge cases: different lengths, one array empty, equal values, negatives.
The idea. Like two queues of students: look at the front of each, send the smaller one to the new list, and that queue moves up. Because both arrays are sorted, the smallest value left is always at one of the two fronts. i is the front of a, j the front of b, k where the next value goes in c.
The obvious attempt: stop when one array runs out
#include <stdio.h>
int main() {
int n, m, a[100], b[100], c[200];
scanf("%d", &n);
for (int i = 0; i < n; i++) scanf("%d", &a[i]);
scanf("%d", &m);
for (int j = 0; j < m; j++) scanf("%d", &b[j]);
int i = 0, j = 0, k = 0;
while (i < n && j < m) {
if (a[i] <= b[j]) c[k++] = a[i++];
else c[k++] = b[j++];
}
for (int t = 0; t < k; t++) printf("%d ", c[t]);
printf("\n");
return 0;
}
Input 3 / 1 3 5 / 5 / 2 4 6 8 10:
1 2 3 4 5
Why: one array ran out first
After 5 is copied, i == n and i < n && j < m is false, so the loop stops. But 6, 8 and 10 are still waiting in b.
c[k++] = a[i++]; means: copy a[i] into c[k], then increase both k and i (the ++ after a name gives the old value, then adds one).
The fix: copy the leftovers
After the loop, copy whatever is left. Only one of the two loops does anything, because one array is already empty, and the leftovers are already sorted.
#include <stdio.h>
int main() {
int n, m, a[100], b[100], c[200];
scanf("%d", &n);
for (int i = 0; i < n; i++) scanf("%d", &a[i]);
scanf("%d", &m);
for (int j = 0; j < m; j++) scanf("%d", &b[j]);
int i = 0, j = 0, k = 0;
while (i < n && j < m) {
if (a[i] <= b[j]) c[k++] = a[i++];
else c[k++] = b[j++];
}
while (i < n) c[k++] = a[i++];
while (j < m) c[k++] = b[j++];
for (int t = 0; t < k; t++) printf("%d ", c[t]);
printf("\n");
return 0;
}
Input 3 / 1 3 5 / 5 / 2 4 6 8 10:
1 2 3 4 5 6 8 10
Input 3 / 4 5 6 / 0:
4 5 6
Input 3 / -2 2 2 / 3 / -5 2 9:
-5 -2 2 2 2 9
Input 0 / 2 / 1 1:
1 1
Stable merge. a[i] <= b[j] (not <) takes a's value first on a tie, so equal values keep their original order (all of a's before b's). This is called stable, and it matters when sorting records (two students with the same marks keep their roll-number order). Merge sort is built on exactly this merge.
Complexity: every value is copied once: O(n + m) time; the new array c: O(n + m) space.
Concatenating and calling qsort also works, but costs O((n + m) log(n + m)) and throws away the fact that both halves are already sorted.
Q2: Union and intersection of sorted arrays
Problem. Two sorted arrays; values may repeat. The union is every value that is in a or in b. The intersection is every value that is in both. Print each value once.
| a | b | union | intersection |
|---|---|---|---|
1 2 2 3 |
2 2 2 4 |
1 2 3 4 | 2 |
-3 1 |
2 5 5 |
-3 1 2 5 | (nothing) |
| (empty) | 7 7 8 |
7 8 | (nothing) |
1 3 3 5 7 9 |
3 3 4 7 9 |
1 3 4 5 7 9 | 3 7 9 |
The obvious attempts
The union as a plain merge (the Q1 program):
Input 4 / 1 2 2 3 / 4 / 2 2 2 4:
1 2 2 2 2 2 3 4
2 is printed five times. The intersection by searching b for every a[i]:
#include <stdio.h>
int main() {
int n, m, a[100], b[100];
scanf("%d", &n);
for (int i = 0; i < n; i++) scanf("%d", &a[i]);
scanf("%d", &m);
for (int j = 0; j < m; j++) scanf("%d", &b[j]);
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
if (a[i] == b[j]) {
printf("%d ", a[i]);
break;
}
printf("\n");
return 0;
}
Input 4 / 1 2 2 3 / 4 / 2 2 2 4:
2 2
2 is printed twice (once for each 2 in a), and every a[i] scans all of b: O(n · m).
The fix: put() remembers the last printed value
A small helper prints x only if it differs from the last value it printed. The output is sorted, so copies come one after another and one comparison is enough. Two global variables (declared outside every function, so every function can use them and they live for the whole program): last is the last value printed, has says whether anything was printed yet (so the very first value is always printed, whatever last holds).
- Union: the merge, with every value going through
put(). - Intersection: two pointers. If
a[i] < b[j],a[i]can't be inb(everything afterb[j]is bigger), soi++; the mirror casej++; equal →putit and move both.
#include <stdio.h>
int last, has = 0;
void put(int x) {
if (has && x == last) return;
printf("%d ", x);
last = x;
has = 1;
}
int main() {
int n, m, a[100], b[100];
scanf("%d", &n);
for (int i = 0; i < n; i++) scanf("%d", &a[i]);
scanf("%d", &m);
for (int j = 0; j < m; j++) scanf("%d", &b[j]);
int i = 0, j = 0;
while (i < n && j < m) {
if (a[i] <= b[j]) put(a[i++]);
else put(b[j++]);
}
while (i < n) put(a[i++]);
while (j < m) put(b[j++]);
printf("\n");
return 0;
}
Input 4 / 1 2 2 3 / 4 / 2 2 2 4:
1 2 3 4
Input 2 / -3 1 / 3 / 2 5 5:
-3 1 2 5
Input 0 / 3 / 7 7 8:
7 8
Input 6 / 1 3 3 5 7 9 / 5 / 3 3 4 7 9:
1 3 4 5 7 9
#include <stdio.h>
int last, has = 0;
void put(int x) {
if (has && x == last) return;
printf("%d ", x);
last = x;
has = 1;
}
int main() {
int n, m, a[100], b[100];
scanf("%d", &n);
for (int i = 0; i < n; i++) scanf("%d", &a[i]);
scanf("%d", &m);
for (int j = 0; j < m; j++) scanf("%d", &b[j]);
int i = 0, j = 0;
while (i < n && j < m) {
if (a[i] < b[j]) i++;
else if (a[i] > b[j]) j++;
else {
put(a[i]);
i++;
j++;
}
}
printf("\n");
return 0;
}
Input 4 / 1 2 2 3 / 4 / 2 2 2 4:
2
Input 2 / -3 1 / 3 / 2 5 5:
Input 6 / 1 3 3 5 7 9 / 5 / 3 3 4 7 9:
3 7 9
Input 0 / 3 / 7 7 8:
(An empty line means nothing in common.)
Complexity: each step moves at least one pointer: O(n + m) time, O(1) extra space.
Q3: Maximum subarray sum
A subarray is one or more consecutive elements a[i] … a[j] (nothing skipped). An array of n elements has n(n + 1)/2 subarrays. (A subsequence may skip elements; that is a different question.)
Problem. Read n, then n integers. Print the largest sum of any subarray. The subarray can't be empty.
| Input | Output |
|---|---|
9 / -2 1 -3 4 -1 2 1 -5 4 |
6 (4 -1 2 1) |
3 / -3 -1 -2 |
-1 (just the -1) |
4 / 2 3 1 5 |
11 (the whole array) |
1 / -7 |
-7 |
Edge cases: all negative, all positive, n = 1, big n.
The obvious attempt: every subarray
For each start i, extend the end j one step at a time with a running sum.
#include <stdio.h>
int main() {
int n, a[100];
scanf("%d", &n);
for (int i = 0; i < n; i++) scanf("%d", &a[i]);
int best = a[0];
for (int i = 0; i < n; i++) {
int sum = 0;
for (int j = i; j < n; j++) {
sum += a[j];
if (sum > best) best = sum;
}
}
printf("max sum %d\n", best);
return 0;
}
Input 9 / -2 1 -3 4 -1 2 1 -5 4:
max sum 6
Input 3 / -3 -1 -2:
max sum -1
Correct, but O(n²). The stress test (300,000 days made by the program, a[i] = i % 10 - 4):
#include <stdio.h>
int a[300000];
int main() {
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++) a[i] = i % 10 - 4;
int best = a[0];
for (int i = 0; i < n; i++) {
int sum = 0;
for (int j = i; j < n; j++) {
sum += a[j];
if (sum > best) best = sum;
}
}
printf("max sum %d\n", best);
return 0;
}
Input 300000:
Time Limit Exceeded (stopped after 8 seconds)
About 45 billion subarrays.
The idea: Kadane's algorithm
Walk once and keep cur = the best sum of a subarray that ends exactly at i. For position i there are only two choices: extend the best run ending at i - 1 (cur + a[i]), or start fresh at i (a[i]). Take the bigger one:
cur = max(a[i], cur + a[i])
best = max(best, cur)
In shop terms: if the run so far is in loss (cur < 0), it can only drag today down, so drop it and start again today.
a: -2 1 -3 4 -1 2 1 -5 4
cur: -2 1 -2 4 3 5 6 1 5
best: -2 1 1 4 4 5 6 6 6
The common wrong version: best = 0
#include <stdio.h>
int main() {
int n, a[100];
scanf("%d", &n);
for (int i = 0; i < n; i++) scanf("%d", &a[i]);
int cur = 0, best = 0;
for (int i = 0; i < n; i++) {
cur += a[i];
if (cur > best) best = cur;
if (cur < 0) cur = 0;
}
printf("max sum %d\n", best);
return 0;
}
Input 9 / -2 1 -3 4 -1 2 1 -5 4:
max sum 6
Input 3 / -3 -1 -2:
max sum 0
best = 0 pretends there is a subarray with sum 0, the empty one, which the question doesn't allow. With all negatives, no real sum beats 0. (This version is correct only if the problem says an empty subarray, sum 0, is allowed.)
The fix: start at a[0]
#include <stdio.h>
int main() {
int n, a[100];
scanf("%d", &n);
if (n < 1 || n > 100) {
printf("n must be 1 to 100\n");
return 0;
}
for (int i = 0; i < n; i++) scanf("%d", &a[i]);
int cur = a[0], best = a[0];
for (int i = 1; i < n; i++) {
if (cur + a[i] > a[i]) cur = cur + a[i];
else cur = a[i];
if (cur > best) best = cur;
}
printf("max sum %d\n", best);
return 0;
}
Input 3 / -3 -1 -2:
max sum -1
Input 9 / -2 1 -3 4 -1 2 1 -5 4:
max sum 6
Input 4 / 2 3 1 5:
max sum 11
Input 1 / -7:
max sum -7
The stress test:
#include <stdio.h>
int a[300000];
int main() {
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++) a[i] = i % 10 - 4;
int cur = a[0], best = a[0];
for (int i = 1; i < n; i++) {
if (cur + a[i] > a[i]) cur = cur + a[i];
else cur = a[i];
if (cur > best) best = cur;
}
printf("max sum %d\n", best);
return 0;
}
Input 300000:
max sum 150010
Complexity: one pass, O(n) time, O(1) extra space.
Overflow note. Here the values are small. With n up to 10⁵ and values up to 10⁹ in size, sums reach 10¹⁴: use long long cur, best.
Why Kadane is correct (sketch). Any best subarray ends somewhere, say at i. cur at i is the best sum over all subarrays ending at i (by induction: the best one ending at i is either a[i] alone or a[i] added to the best one ending at i - 1). best is the maximum over all i. This "best answer ending here" idea is a first taste of dynamic programming.
Complexity summary
| Question | Method | Time | Extra space |
|---|---|---|---|
| Merge | stop when one runs out | O(n + m), wrong | O(n + m) |
| two pointers + leftovers | O(n + m) | O(n + m) | |
concatenate + qsort |
O((n + m) log(n + m)) | O(n + m) | |
| Union | plain merge | O(n + m), repeats | O(1) |
merge through put() |
O(n + m) | O(1) | |
| Intersection | search b for each a[i] |
O(n · m), repeats | O(1) |
two pointers + put() |
O(n + m) | O(1) | |
| Max subarray | every subarray | O(n²) | O(1) |
| Kadane | O(n) | O(1) |
Common mistakes (and the real results)
| Mistake | What you see | Why | Fix |
|---|---|---|---|
merge loop while (i < n && j < m) only |
no error: 1 2 3 4 5 (6, 8, 10 lost) |
one array still has values | copy the leftovers of a and b |
a[i] < b[j] in the merge |
correct values, but ties take b first |
not stable | <= |
| union as a plain merge | no error: 2 printed five times |
every copy is printed | put(): skip the last printed value |
intersection: search b for every a[i] |
no error: 2 2, and O(n · m) |
each copy in a prints again |
two pointers, move both on a match |
| every subarray for 300,000 values | Time Limit Exceeded |
O(n²) | Kadane |
int cur = 0, best = 0; |
no error: max sum 0 for -3 -1 -2 |
0 is the empty subarray | start cur and best at a[0] |
int sums with big values |
wrong sums (UB) | sums pass INT_MAX |
long long |
Your turn: where is the best subarray? (solution)
Problem. Same input as Q3. Print the best sum and the indexes where that subarray starts and ends. -2 1 -3 4 -1 2 1 -5 4 → 6 from index 3 to 6.
Idea. Keep s, the index where cur last started fresh. Whenever best improves, copy s into bs and i into be. Still one pass: O(n), O(1).
Show the solution
#include <stdio.h>
int main() {
int n, a[100];
scanf("%d", &n);
if (n < 1 || n > 100) {
printf("n must be 1 to 100\n");
return 0;
}
for (int i = 0; i < n; i++) scanf("%d", &a[i]);
int cur = a[0], best = a[0];
int s = 0, bs = 0, be = 0;
for (int i = 1; i < n; i++) {
if (cur + a[i] > a[i]) cur = cur + a[i];
else {
cur = a[i];
s = i;
}
if (cur > best) {
best = cur;
bs = s;
be = i;
}
}
printf("max sum %d from index %d to %d\n", best, bs, be);
return 0;
}
Input 9 / -2 1 -3 4 -1 2 1 -5 4:
max sum 6 from index 3 to 6
Input 3 / -3 -1 -2:
max sum -1 from index 1 to 1
Input 4 / 2 3 1 5:
max sum 11 from index 0 to 3
Input 1 / -7:
max sum -7 from index 0 to 0
Practice questions (with solutions)
1. Merge three sorted arrays. Merge the first two, then merge the result with the third (each merge is the Q1 function). O(n₁ + n₂ + n₃) per merge.
Solution
#include <stdio.h>
int merge(int a[], int n, int b[], int m, int c[]) {
int i = 0, j = 0, k = 0;
while (i < n && j < m) {
if (a[i] <= b[j]) c[k++] = a[i++];
else c[k++] = b[j++];
}
while (i < n) c[k++] = a[i++];
while (j < m) c[k++] = b[j++];
return k;
}
int main() {
int a[] = {1, 4, 9}, b[] = {2, 3, 10, 11}, d[] = {0, 5};
int ab[7], all[9];
int k = merge(a, 3, b, 4, ab);
k = merge(ab, k, d, 2, all);
for (int i = 0; i < k; i++) printf("%d ", all[i]);
printf("\n");
return 0;
}
Output:
0 1 2 3 4 5 9 10 11
2. Intersection that keeps repeats. 1 2 2 3 and 2 2 2 3 3 → 2 2 3 (each match uses one copy from each side). The Q2 two pointers without put(): print on every match and move both.
Solution
#include <stdio.h>
int main() {
int a[] = {1, 2, 2, 3}, b[] = {2, 2, 2, 3, 3};
int n = 4, m = 5, i = 0, j = 0;
while (i < n && j < m) {
if (a[i] < b[j]) i++;
else if (a[i] > b[j]) j++;
else {
printf("%d ", a[i]);
i++;
j++;
}
}
printf("\n");
return 0;
}
Output:
2 2 3
3. Maximum sum of a subarray of length exactly k. A sliding window: sum the first k, then for each step add the new element and subtract the one that left. O(n).
Solution
#include <stdio.h>
int main() {
int n, k, a[100];
scanf("%d %d", &n, &k);
if (n < 1 || n > 100 || k < 1 || k > n) {
printf("need 1 <= k <= n <= 100\n");
return 0;
}
for (int i = 0; i < n; i++) scanf("%d", &a[i]);
long long sum = 0;
for (int i = 0; i < k; i++) sum += a[i];
long long best = sum;
for (int i = k; i < n; i++) {
sum += a[i] - a[i - k];
if (sum > best) best = sum;
}
printf("best %d-day sum %lld\n", k, best);
return 0;
}
Input 7 3 / 2 -1 4 -2 6 -3 1:
best 3-day sum 8
Input 3 3 / -1 -2 -3:
best 3-day sum -6
Quick quiz
#include <stdio.h>
int main() {
int a[] = {-2, 3, -1, 4, -5};
int cur = a[0], best = a[0];
for (int i = 1; i < 5; i++) {
if (cur + a[i] > a[i]) cur = cur + a[i];
else cur = a[i];
if (cur > best) best = cur;
}
printf("%d\n", best);
return 0;
}
(A) 6 (B) 7 (C) 4 (D) 3
Answer
(A) 6. cur: -2 → 3 (start fresh) → 2 → 6 → 1. The best subarray is 3 -1 4.
Output:
6
Interview questions
- Merge two sorted arrays in O(n + m). Two pointers, copy the smaller front, then the leftovers.
- What is a stable merge and why
<=? On a tie the left array's value goes first, so equal values keep their order. - Merge in place when
ahas room forbat its end (LeetCode 88)? Fill from the back: compare the largest values and write ata[n + m - 1]downwards. - Union and intersection of sorted arrays without duplicates. Two pointers; skip a value equal to the last printed one.
- What if the arrays are not sorted? Sort first (O(n log n)), or use a hash set (not built into C).
- Subarray vs subsequence? A subarray is consecutive; a subsequence may skip elements.
- Explain Kadane's algorithm.
cur = max(a[i], cur + a[i]),best = max(best, cur); O(n), O(1). - Why does
best = 0fail? It allows the empty subarray; all negative inputs print 0. - Return the subarray too. Track where
curstarted fresh and copy it whenbestimproves.
Glossary
| Term | Meaning | Example |
|---|---|---|
| Merge | Combining two sorted arrays into one sorted array | 1 3 5 + 2 4 → 1 2 3 4 5 |
| Two pointers | Two indexes moved through arrays by simple rules | i in a, j in b |
| Front | The next unused element of an array | a[i] |
| Leftovers | Values still left in one array when the other runs out | 6 8 10 |
Post-increment x++ |
Use the old value, then add one | c[k++] = a[i++]; |
| Stable | Equal values keep their original order | <= in the merge |
| Union | Every value in a or b, once |
1 2 3 4 |
| Intersection | Every value in both a and b |
2 |
| Duplicate / repeat | A value that appears more than once | 2 2 |
| Global variable | Declared outside every function; visible everywhere, lives for the whole program | int last, has = 0; |
| Helper function | A small function that does one job for the others | put(x) |
| Subarray | One or more consecutive elements | 4 -1 2 1 |
| Subsequence | Elements in order, skipping allowed | 1 4 2 from 1 -3 4 -1 2 |
| Maximum subarray sum | The largest sum over all subarrays | 6 |
| Kadane's algorithm | One pass keeping the best sum ending here | cur = max(a[i], cur + a[i]) |
| Running sum | A sum updated one element at a time | sum += a[j] |
| Empty subarray | No elements, sum 0; not allowed here | why best = 0 fails |
| Sliding window | A fixed-length range moved one step at a time | sum of k days |
| Dynamic programming | Building an answer from the best answers to smaller parts | best sum ending at i |
| Stress test | A huge input to test speed | 300,000 days |
| O(n + m) | Work grows with the total size of both inputs | merging |
| O(n · m) | Every element of one against every element of the other | searching b for each a[i] |
| O(n²) | Double the input, four times the work | every subarray |
Summary
- Merge: copy the smaller front, then the leftovers;
<=keeps it stable. O(n + m). - Union / intersection: two pointers and a
put()that skips the last printed value. O(n + m), O(1). - Maximum subarray sum: brute force is O(n²); Kadane extends or starts fresh in one pass, starting from
a[0]so all-negative arrays work.
Next episode: Searching questions: linear vs binary search with an overflow-safe middle, the first and last occurrence of a value, and counting occurrences in a sorted array.