SyntaxPilot
Courses/C Coding Questions/Lesson 11
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

C Coding Questions · Lesson 11 of 30

Array questions V

merge two sorted arraysunion and intersection of sorted arraysmaximum subarray sum (Kadane's algorithm, all-negative case)

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 in b (everything after b[j] is bigger), so i++; the mirror case j++; equal → put it 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

  1. Merge two sorted arrays in O(n + m). Two pointers, copy the smaller front, then the leftovers.
  2. What is a stable merge and why <=? On a tie the left array's value goes first, so equal values keep their order.
  3. Merge in place when a has room for b at its end (LeetCode 88)? Fill from the back: compare the largest values and write at a[n + m - 1] downwards.
  4. Union and intersection of sorted arrays without duplicates. Two pointers; skip a value equal to the last printed one.
  5. What if the arrays are not sorted? Sort first (O(n log n)), or use a hash set (not built into C).
  6. Subarray vs subsequence? A subarray is consecutive; a subsequence may skip elements.
  7. Explain Kadane's algorithm. cur = max(a[i], cur + a[i]), best = max(best, cur); O(n), O(1).
  8. Why does best = 0 fail? It allows the empty subarray; all negative inputs print 0.
  9. Return the subarray too. Track where cur started fresh and copy it when best improves.

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.