SyntaxPilot
Courses/C Coding Questions/Lesson 8
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 8 of 30

Array questions II

reverse an array in placerotate by k (reversal trick)left rotate by one; k larger than n

These are the notes for C Coding Questions, episode 8, placement practice for people who finished the SyntaxPilot C course. Array questions, part two: moving elements around inside an array. Reverse an array in place, left rotate by one, and rotate by k with the reversal trick, including k larger than the array.

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.

In place and rotation: a queue at a ticket counter

At a ticket counter In C
turn the whole queue around, with no second hall to move into reverse in place: inside the same array, no second array
the person at the front walks to the back, everyone steps forward left rotation by one: 1 2 3 4 5 → 2 3 4 5 1
k people walk to the back, one after another left rotation by k
all 5 people of a 5-person queue walk to the back the same queue: only k % n matters
  • In place means the algorithm changes the array itself and uses only O(1) extra space (a few variables), not a second array of size n.
  • A left rotation by k moves the first k elements to the end, keeping their order. A right rotation moves the last k to the front.
  • Two pointers here simply means two index variables that move through the array, usually one from each end.

Q1: Reverse an array in place

Problem. Read n, then n integers. Reverse the array without a second array, and print it.

Input Output
5 / 1 2 3 4 5 5 4 3 2 1
4 / 1 2 3 4 4 3 2 1
1 / 42 42

Edge cases: odd n (one element stays in the middle), even n, n = 1.

Think out loud

The first and the last swap places, then the second and the second-last, and so on. The partner of index i is index n - 1 - i: 0 ↔ 4, 1 ↔ 3, and index 2 (the middle) stays.

The obvious attempt: swap every i with its partner

#include <stdio.h>

int main() {
    int n, a[100];
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);
    for (int i = 0; i < n; i++) {
        int t = a[i];
        a[i] = a[n - 1 - i];
        a[n - 1 - i] = t;
    }
    for (int i = 0; i < n; i++) printf("%d ", a[i]);
    printf("\n");
    return 0;
}

Input 5 1 2 3 4 5:

1 2 3 4 5 

Why: every pair was swapped twice

A dry run (following the code by hand):

i = 0: swap a[0], a[4]  ->  5 2 3 4 1
i = 1: swap a[1], a[3]  ->  5 4 3 2 1   (reversed!)
i = 2: swap a[2], a[2]  ->  5 4 3 2 1
i = 3: swap a[3], a[1]  ->  5 2 3 4 1   (undoes i = 1)
i = 4: swap a[4], a[0]  ->  1 2 3 4 5   (undoes i = 0)

The loop must stop at the middle. Use two pointers l (from the left) and r (from the right): swap, move them towards each other, stop when they meet (l < r fails).

The fix: two pointers

#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 l = 0, r = n - 1;
    while (l < r) {
        int t = a[l];
        a[l] = a[r];
        a[r] = t;
        l++;
        r--;
    }
    for (int i = 0; i < n; i++) printf("%d ", a[i]);
    printf("\n");
    return 0;
}

Input 5 1 2 3 4 5:

5 4 3 2 1 

Input 4 1 2 3 4:

4 3 2 1 

Input 1 42:

42 

Input 6 -1 0 7 7 3 9:

9 3 7 7 0 -1 

Complexity: n/2 swaps, which is still O(n) time; O(1) extra space (one temporary t). (Looping i < n / 2 with a[n - 1 - i] is the same fix.)

Q2: Left rotate by one

Problem. Read n, then n integers. Rotate the array left by one and print it.

Input Output
5 / 1 2 3 4 5 2 3 4 5 1
1 / 7 7

The obvious attempt: shift, then copy a[0] to the end

#include <stdio.h>

int main() {
    int n, a[100];
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);
    for (int i = 0; i < n - 1; i++) a[i] = a[i + 1];
    a[n - 1] = a[0];
    for (int i = 0; i < n; i++) printf("%d ", a[i]);
    printf("\n");
    return 0;
}

Input 5 1 2 3 4 5:

2 3 4 5 2 

Why: a[0] was already overwritten

After the shift the array is 2 3 4 5 5. The very first step, a[0] = a[1], overwrote the 1, so a[n - 1] = a[0] copies a 2. Save a value before you overwrite it: int first = a[0]; before the shift.

The fix

#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 first = a[0];
    for (int i = 0; i < n - 1; i++) a[i] = a[i + 1];
    a[n - 1] = first;
    for (int i = 0; i < n; i++) printf("%d ", a[i]);
    printf("\n");
    return 0;
}

Input 5 1 2 3 4 5:

2 3 4 5 1 

Input 1 7:

7 

Input 3 9 -4 9:

-4 9 9 

Complexity: O(n) time, O(1) extra space.

Q3: Rotate left by k

Problem. Read n and k, then n integers. Rotate the array left by k (k ≥ 0, possibly much bigger than n) and print it.

Input Output
7 2 / 1 2 3 4 5 6 7 3 4 5 6 7 1 2
7 9 / 1 2 3 4 5 6 7 3 4 5 6 7 1 2 (9 = 7 + 2)
7 0 or 7 7 unchanged
7 2000000000 6 7 1 2 3 4 5 (2,000,000,000 % 7 = 5)

Edge cases: k = 0, k = n, k > n, a huge k, a huge array.

The obvious attempt: rotate by one, k times

#include <stdio.h>

void rotate_one(int a[], int n) {
    int first = a[0];
    for (int i = 0; i < n - 1; i++) a[i] = a[i + 1];
    a[n - 1] = first;
}

int main() {
    int n, k, a[100];
    scanf("%d %d", &n, &k);
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);
    for (int r = 0; r < k; r++) rotate_one(a, n);
    for (int i = 0; i < n; i++) printf("%d ", a[i]);
    printf("\n");
    return 0;
}

Input 7 2 1 2 3 4 5 6 7:

3 4 5 6 7 1 2 

Input 7 9 1 2 3 4 5 6 7:

3 4 5 6 7 1 2 

Input 7 2000000000 1 2 3 4 5 6 7:

Time Limit Exceeded (stopped after 8 seconds)

Why: k rotations of n moves each

Each rotate_one moves all n elements, and we call it k times: O(n · k). Two billion rotations is far too many, even for seven numbers. But n rotations bring the array back to where it started, so only the remainder matters: k = k % n (here 2,000,000,000 % 7 = 5).

#include <stdio.h>

void rotate_one(int a[], int n) {
    int first = a[0];
    for (int i = 0; i < n - 1; i++) a[i] = a[i + 1];
    a[n - 1] = first;
}

int main() {
    int n, k, a[100];
    scanf("%d %d", &n, &k);
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);
    k = k % n;
    for (int r = 0; r < k; r++) rotate_one(a, n);
    for (int i = 0; i < n; i++) printf("%d ", a[i]);
    printf("\n");
    return 0;
}

Input 7 2000000000 1 2 3 4 5 6 7:

6 7 1 2 3 4 5 

Still too slow for a big array: a stress test

k % n fixes a huge k, but k can still be up to n − 1, so the time is still O(n · k). A stress test runs the code on a big input; here the program makes the input itself (the array 1 to n), because typing a million numbers isn't practical. Globals like int a[1000000]; live outside main, so a big array doesn't overflow the stack (the memory for local variables).

#include <stdio.h>

int a[1000000];

void rotate_one(int a[], int n) {
    int first = a[0];
    for (int i = 0; i < n - 1; i++) a[i] = a[i + 1];
    a[n - 1] = first;
}

int main() {
    int n, k;
    scanf("%d %d", &n, &k);
    for (int i = 0; i < n; i++) a[i] = i + 1;
    k = k % n;
    for (int r = 0; r < k; r++) rotate_one(a, n);
    printf("%d %d ... %d\n", a[0], a[1], a[n - 1]);
    return 0;
}

Input 1000000 500000:

Time Limit Exceeded (stopped after 8 seconds)

Half a million rotations of a million numbers is 500 billion moves.

The reversal trick

A left rotation by k swaps two blocks: the first k elements, and the rest. Three reversals do it:

1 2 | 3 4 5 6 7      split after the first k = 2
2 1 | 3 4 5 6 7      reverse the first k        reverse(a, 0, k - 1)
2 1 | 7 6 5 4 3      reverse the rest           reverse(a, k, n - 1)
3 4 5 6 7 1 2        reverse the whole array    reverse(a, 0, n - 1)

Reversing the whole array puts the two blocks in swapped order but each one backwards; the two earlier reversals made each block backwards in advance, so they come out the right way round. Every element moves about twice: O(n) time for any k, and O(1) extra space.

Do k = k % n first. Without it, k = 9 on 7 elements would call reverse(a, 0, 8), which reads and writes past the end of the array: undefined behaviour.

#include <stdio.h>

void reverse(int a[], int l, int r) {
    while (l < r) {
        int t = a[l];
        a[l] = a[r];
        a[r] = t;
        l++;
        r--;
    }
}

int main() {
    int n, k, a[100];
    scanf("%d %d", &n, &k);
    if (n < 1 || n > 100 || k < 0) {
        printf("need 1 <= n <= 100 and k >= 0\n");
        return 0;
    }
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);
    k = k % n;
    reverse(a, 0, k - 1);
    reverse(a, k, n - 1);
    reverse(a, 0, n - 1);
    for (int i = 0; i < n; i++) printf("%d ", a[i]);
    printf("\n");
    return 0;
}

Input 7 2 1 2 3 4 5 6 7:

3 4 5 6 7 1 2 

Input 7 9 1 2 3 4 5 6 7:

3 4 5 6 7 1 2 

Input 7 0 1 2 3 4 5 6 7:

1 2 3 4 5 6 7 

Input 7 7 1 2 3 4 5 6 7:

1 2 3 4 5 6 7 

Input 7 2000000000 1 2 3 4 5 6 7:

6 7 1 2 3 4 5 

Input 7 -1 1 2 3 4 5 6 7:

need 1 <= n <= 100 and k >= 0

Input 1 5 42:

42 

The same three reversals on the stress test that timed out:

#include <stdio.h>

int a[1000000];

void reverse(int a[], int l, int r) {
    while (l < r) {
        int t = a[l];
        a[l] = a[r];
        a[r] = t;
        l++;
        r--;
    }
}

int main() {
    int n, k;
    scanf("%d %d", &n, &k);
    for (int i = 0; i < n; i++) a[i] = i + 1;
    k = k % n;
    reverse(a, 0, k - 1);
    reverse(a, k, n - 1);
    reverse(a, 0, n - 1);
    printf("%d %d ... %d\n", a[0], a[1], a[n - 1]);
    return 0;
}

Input 1000000 500000:

500001 500002 ... 500000

Instant.

Complexity summary

Question Method Time Extra space
Reverse swap every i with its partner O(n), but wrong (reverses twice) O(1)
two pointers, while (l < r) O(n) O(1)
Rotate by one shift, save a[0] first O(n) O(1)
Rotate by k rotate by one, k times O(n · k) O(1)
with k % n O(n · (k % n)) O(1)
copy into a second array: b[i] = a[(i + k) % n] O(n) O(n)
three reversals O(n) O(1)

Common mistakes (and the real results)

Mistake What you see Why Fix
for (i = 0; i < n; i++) swapping a[i], a[n-1-i] no error: the array comes back unchanged every pair is swapped twice while (l < r) or i < n / 2
shift left, then a[n - 1] = a[0]; no error: 2 3 4 5 2 a[0] was already overwritten save first = a[0] before shifting
rotate_one called k times Time Limit Exceeded O(n · k) k % n and three reversals
no k % n before the reversals reads past the end of the array (UB) index k − 1 ≥ n k = k % n; first
k % n with n = 0 division by zero (UB, usually a crash) % by 0 check n ≥ 1 first
a negative k -1 % 7 is -1 in C % keeps the sign of the left side reject it, or k = ((k % n) + n) % n

Your turn: rotate right by k (solution)

Problem. Read n k, then n integers; rotate the array right by k (the last k elements move to the front). 7 2 / 1 2 3 4 5 6 7 → 6 7 1 2 3 4 5.

Idea. A right rotation by k is a left rotation by n − k. Or do the three reversals in the other order: reverse the whole array, then the first k, then the rest.

Show the solution
#include <stdio.h>

void reverse(int a[], int l, int r) {
    while (l < r) {
        int t = a[l];
        a[l] = a[r];
        a[r] = t;
        l++;
        r--;
    }
}

int main() {
    int n, k, a[100];
    scanf("%d %d", &n, &k);
    if (n < 1 || n > 100 || k < 0) {
        printf("need 1 <= n <= 100 and k >= 0\n");
        return 0;
    }
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);
    k = k % n;
    reverse(a, 0, n - 1);
    reverse(a, 0, k - 1);
    reverse(a, k, n - 1);
    for (int i = 0; i < n; i++) printf("%d ", a[i]);
    printf("\n");
    return 0;
}

Input 7 2 1 2 3 4 5 6 7:

6 7 1 2 3 4 5 

Input 7 9 1 2 3 4 5 6 7:

6 7 1 2 3 4 5 

Input 7 0 1 2 3 4 5 6 7:

1 2 3 4 5 6 7 

Input 1 5 42:

42 

Time O(n), extra space O(1).

Practice questions (with solutions)

1. Reverse only the part from index l to index r. Input n l r, then the array.

Solution
#include <stdio.h>

int main() {
    int n, l, r, a[100];
    scanf("%d %d %d", &n, &l, &r);
    if (n < 1 || n > 100 || l < 0 || r >= n || l > r) {
        printf("need 0 <= l <= r < n <= 100\n");
        return 0;
    }
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);
    while (l < r) {
        int t = a[l];
        a[l] = a[r];
        a[r] = t;
        l++;
        r--;
    }
    for (int i = 0; i < n; i++) printf("%d ", a[i]);
    printf("\n");
    return 0;
}

Input 7 1 4 1 2 3 4 5 6 7:

1 5 4 3 2 6 7 

Input 5 0 4 1 2 3 4 5:

5 4 3 2 1 

Input 5 3 1 1 2 3 4 5:

need 0 <= l <= r < n <= 100

2. Is the array a palindrome? (It reads the same both ways.) Two pointers that compare instead of swapping.

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 l = 0, r = n - 1, ok = 1;
    while (l < r) {
        if (a[l] != a[r]) {
            ok = 0;
            break;
        }
        l++;
        r--;
    }
    printf(ok ? "palindrome\n" : "not a palindrome\n");
    return 0;
}

Input 5 1 2 3 2 1:

palindrome

Input 4 1 2 2 1:

palindrome

Input 3 1 2 3:

not a palindrome

Input 1 9:

palindrome

3. Rotate a string left by k characters. The same three reversals on a char array; strlen gives n. %100s reads at most 100 characters into the 101-byte array (one byte for the closing '\0').

Solution
#include <stdio.h>
#include <string.h>

void reverse(char s[], int l, int r) {
    while (l < r) {
        char t = s[l];
        s[l] = s[r];
        s[r] = t;
        l++;
        r--;
    }
}

int main() {
    char s[101];
    int k;
    scanf("%100s %d", s, &k);
    int n = strlen(s);
    if (k < 0) {
        printf("k must be 0 or more\n");
        return 0;
    }
    k = k % n;
    reverse(s, 0, k - 1);
    reverse(s, k, n - 1);
    reverse(s, 0, n - 1);
    printf("%s\n", s);
    return 0;
}

Input syntaxpilot 3:

taxpilotsyn

Input abcde 7:

cdeab

Input a 0:

a

Quick quiz

int a[] = {1, 2, 3, 4, 5, 6};
int l = 0, r = 5;
while (l < r) {
    int t = a[l]; a[l] = a[r]; a[r] = t;
    l += 2; r -= 2;
}
for (int i = 0; i < 6; i++) printf("%d ", a[i]);

(A) 6 2 4 3 5 1 (B) 6 5 4 3 2 1 (C) 6 2 3 4 5 1 (D) 1 2 3 4 5 6

Answer

(A). l = 0, r = 5 swap 1 and 6; l = 2, r = 3 swap 3 and 4; then l = 4 > r = 1, so the loop stops.

Output:

6 2 4 3 5 1 

Interview questions

  1. Reverse an array in place. Two pointers from both ends, swap, move inwards, stop when they meet. O(n), O(1).
  2. Rotate an array by k in O(n) time and O(1) space. k %= n, then reverse the first k, reverse the rest, reverse everything.
  3. Why k % n? n rotations give back the same array; it also keeps the indexes inside the array.
  4. What other O(n) methods exist? A second array (b[i] = a[(i + k) % n], O(n) extra space), or the juggling algorithm (cycles of length n / gcd(n, k), O(1) space).
  5. Left rotation by k vs right rotation by k? Right by k = left by n − k.
  6. What is a stress test? Running the code on large or random inputs to check speed and correctness, often against a slow but simple solution.
  7. Why might a big local array crash? Local arrays live on the stack, which is limited (often 8 MB); put very big arrays at global scope or allocate them with malloc.

Glossary

Term Meaning Example
In place Changing the array itself with O(1) extra space reverse with swaps
Swap Exchanging two values through a temporary t = a[l]; a[l] = a[r]; a[r] = t;
Temporary variable A variable that holds a value for a moment t, first
Two pointers Two index variables moving through an array l from the left, r from the right
Dry run Following code by hand, step by step the "swapped twice" table
Left rotation by k The first k elements move to the end 1 2 3 4 5, k = 2 → 3 4 5 1 2
Right rotation by k The last k elements move to the front k = 2 → 4 5 1 2 3
Remainder % What is left after division 9 % 7 = 2
Function A named block of code you can call reverse(a, l, r)
Reversal trick Rotation by three reversals reverse k, rest, all
Stress test A big input to test speed and correctness a million numbers
Global variable Declared outside every function; lives for the whole program int a[1000000];
Stack The limited memory for local variables a huge local array can overflow it
Time Limit Exceeded (TLE) The judge stopped a program that ran too long 8 seconds here
O(n · k) Work grows with n times k k rotations of n moves
O(n) Double the input, double the work three reversals
O(1) extra space A fixed number of extra variables no second array
Undefined behaviour (UB) The C standard doesn't define what happens a[n], k % 0
Palindrome Reads the same forwards and backwards 1 2 3 2 1

Summary

  • Reverse in place with two pointers that stop when they meet; going all the way swaps every pair twice.
  • Rotate by one: save a[0] before shifting.
  • Rotate by k: only k % n matters; rotating one step at a time is O(n · k), too slow.
  • The reversal trick (reverse the first k, the rest, then everything) is O(n) time and O(1) extra space; do k % n first.

Next episode: Array questions III: remove duplicates from a sorted array, the frequency of each element, and the missing number from 1 to n (sum and XOR).