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
- Reverse an array in place. Two pointers from both ends, swap, move inwards, stop when they meet. O(n), O(1).
- 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. - Why
k % n? n rotations give back the same array; it also keeps the indexes inside the array. - 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). - Left rotation by k vs right rotation by k? Right by k = left by n − k.
- 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.
- 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 % nmatters; 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 % nfirst.
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).