Tag array algorithms

Rotate an Array by d – Counterclockwise or Left in C: A Comprehensive Tutorial

Left rotation (counterclockwise rotation) of an array by d positions shifts each element d positions to the left, with elements wrapping around from the beginning to the end. Understanding left rotation is essential for solving problems involving circular data, rotated sorted arrays, and algorithmic challenges.

This tutorial provides an in-depth exploration of left array rotation in C: multiple approaches, time and space complexities, practical applications, common pitfalls, and best practices.

---

Conceptual Introduction & Fundamentals

What is Left Rotation?

Left rotation (counterclockwise rotation) by d positions moves each element d positions to the left. Elements that go past index 0 wrap around to the end.

Example:

text

Original: [1, 2, 3, 4, 5, 6], d = 2 Rotated: [3, 4, 5, 6, 1, 2]

Step-by-step:

text

Start: [1, 2, 3, 4, 5, 6] After 1: [2, 3, 4, 5, 6, 1] After 2: [3, 4, 5, 6, 1, 2]

Why Left Rotation Matters

• Circular buffers: Implement queues and ring buffers.
• Rotated sorted arrays: Search in O(log n) with modifications.
• String rotation: Check if one string is a rotation of another.
• Data processing: Shift data windows forward.
• Cryptography: Caesar cipher (left shift variant).

Approaches Overview

Approach	Time Complexity	Space Complexity
Rotate one by one	O(n × d)	O(1)
Temporary array	O(n)	O(n)
Juggling algorithm	O(n)	O(1)
Reversal algorithm	O(n)	O(1)

Handling d > n

When d > n, reduce using d % n:

text

d = 4, n = 3 → d % n = 1 (equivalent left rotation)

---

Syntax & Core Mechanics

Approach 1: Rotate One by One (Naive)

Rotate the array by one position d times.

c

#include <stdio.h> void rotateLeftOneByOne(int arr[], int n, int d) { if (n <= 1) return; d %= n; if (d == 0) return; for (int i = 0; i < d; i++) { int first = arr[0]; /* Save first element */ /* Shift all elements left by one */ for (int j = 0; j < n - 1; j++) { arr[j] = arr[j + 1]; } arr[n - 1] = first; /* Place first element at end */ } } int main(void) { int arr[] = {1, 2, 3, 4, 5, 6}; int n = sizeof(arr) / sizeof(arr[0]); int d = 2; rotateLeftOneByOne(arr, n, d); for (int i = 0; i < n; i++) { printf("%d ", arr[i]); } printf("\n"); return 0; }

Expected output:

text

3 4 5 6 1 2

Time: O(n × d), Space: O(1)

Approach 2: Temporary Array

Copy the last n - d elements to the front and the first d elements to the back.

c

#include <stdio.h> #include <stdlib.h> void rotateLeftTemp(int arr[], int n, int d) { if (n <= 1) return; d %= n; if (d == 0) return; int *temp = malloc(n * sizeof(int)); if (temp == NULL) { fprintf(stderr, "Memory allocation failed.\n"); return; } /* Copy last n-d elements to front of temp */ for (int i = 0; i < n - d; i++) { temp[i] = arr[d + i]; } /* Copy first d elements to back of temp */ for (int i = 0; i < d; i++) { temp[n - d + i] = arr[i]; } /* Copy back to original */ for (int i = 0; i < n; i++) { arr[i] = temp[i]; } free(temp); } int main(void) { int arr[] = {1, 2, 3, 4, 5, 6}; int n = sizeof(arr) / sizeof(arr[0]); int d = 2; rotateLeftTemp(arr, n, d); for (int i = 0; i < n; i++) { printf("%d ", arr[i]); } printf("\n"); return 0; }

Expected output:

text

3 4 5 6 1 2

Time: O(n), Space: O(n)

Approach 3: Juggling Algorithm

Uses GCD to determine cycles; rotates elements within each cycle.

Key insight: For left rotation, element at index i moves to index (i - d + n) % n. Equivalently, the element that ends up at index i comes from (i + d) % n.

c

#include <stdio.h> int gcd(int a, int b) { while (b) { int temp = b; b = a % b; a = temp; } return a; } void rotateLeftJuggling(int arr[], int n, int d) { if (n <= 1) return; d %= n; if (d == 0) return; int cycles = gcd(n, d); for (int i = 0; i < cycles; i++) { int currIdx = i; int currEle = arr[currIdx]; do { /* For left rotation: next index where current element goes */ int nextIdx = (currIdx - d + n) % n; int nextEle = arr[nextIdx]; arr[nextIdx] = currEle; currEle = nextEle; currIdx = nextIdx; } while (currIdx != i); } } int main(void) { int arr[] = {1, 2, 3, 4, 5, 6}; int n = sizeof(arr) / sizeof(arr[0]); int d = 2; rotateLeftJuggling(arr, n, d); for (int i = 0; i < n; i++) { printf("%d ", arr[i]); } printf("\n"); return 0; }

Expected output:

text

3 4 5 6 1 2

Time: O(n), Space: O(1)

Approach 4: Reversal Algorithm

Reverse the first d elements, then reverse the remaining n - d elements, then reverse the entire array.

c

#include <stdio.h> void reverse(int arr[], int start, int end) { while (start < end) { int temp = arr[start]; arr[start] = arr[end]; arr[end] = temp; start++; end--; } } void rotateLeftReversal(int arr[], int n, int d) { if (n <= 1) return; d %= n; if (d == 0) return; reverse(arr, 0, d - 1); /* Reverse first d elements */ reverse(arr, d, n - 1); /* Reverse remaining n-d elements */ reverse(arr, 0, n - 1); /* Reverse entire array */ } int main(void) { int arr[] = {1, 2, 3, 4, 5, 6}; int n = sizeof(arr) / sizeof(arr[0]); int d = 2; rotateLeftReversal(arr, n, d); for (int i = 0; i < n; i++) { printf("%d ", arr[i]); } printf("\n"); return 0; }

Expected output:

text

3 4 5 6 1 2

Time: O(n), Space: O(1)

---

Full Practical Code Example with Explanation

This program demonstrates all four left rotation approaches with verification, performance comparison, and edge cases.

Program: Left Array Rotation Comparison

c

/** * array_left_rotation.c * Demonstrates multiple approaches to left rotate an array. * Includes verification, timing, and edge case handling. */ #include <stdio.h> #include <stdlib.h> #include <string.h> #include <errno.h> #include <time.h> #define MAX_LINE_LEN 100 #define MAX_SIZE 100000 /* Function prototypes */ void rotateLeftOneByOne(int arr[], int n, int d); void rotateLeftTemp(int arr[], int n, int d); void rotateLeftJuggling(int arr[], int n, int d); void rotateLeftReversal(int arr[], int n, int d); void reverse(int arr[], int start, int end); int gcd(int a, int b); void printArray(const int arr[], int n); int readInteger(const char *prompt, int *outValue); int arraysEqual(const int a[], const int b[], int n); void copyArray(const int src[], int dst[], int n); void demonstrateApproaches(void); void performanceComparison(void); void demonstrateEdgeCases(void); int main(void) { int choice; char buffer[MAX_LINE_LEN]; printf("=== Array Left Rotation (Counterclockwise) Demo ===\n"); while (1) { printf("\n--- Menu ---\n"); printf("1. Demonstrate All Approaches\n"); printf("2. Custom Rotation\n"); printf("3. Performance Comparison\n"); printf("4. Edge Cases\n"); printf("5. Exit\n"); printf("Enter choice: "); fflush(stdout); if (fgets(buffer, sizeof(buffer), stdin) == NULL) { fprintf(stderr, "Error reading choice.\n"); return EXIT_FAILURE; } choice = atoi(buffer); switch (choice) { case 1: demonstrateApproaches(); break; case 2: { int arr[MAX_SIZE]; int n, d, method; if (readInteger("Enter array size (1-100000): ", &n) != 0) { fprintf(stderr, "Invalid size.\n"); break; } if (n < 1 || n > MAX_SIZE) { printf("Size must be 1-%d.\n", MAX_SIZE); break; } printf("Enter %d elements:\n", n); for (int i = 0; i < n; i++) { char prompt[50]; snprintf(prompt, sizeof(prompt), " Element %d: ", i); if (readInteger(prompt, &arr[i]) != 0) { fprintf(stderr, "Invalid input.\n"); n = i; break; } } if (readInteger("Enter rotation count d: ", &d) != 0) { fprintf(stderr, "Invalid d.\n"); break; } printf("\nOriginal: "); printArray(arr, n); printf("\nMethod:\n"); printf("1. One by One\n"); printf("2. Temporary Array\n"); printf("3. Juggling\n"); printf("4. Reversal\n"); printf("Enter method: "); fflush(stdout); if (fgets(buffer, sizeof(buffer), stdin) == NULL) break; method = atoi(buffer); switch (method) { case 1: rotateLeftOneByOne(arr, n, d); break; case 2: rotateLeftTemp(arr, n, d); break; case 3: rotateLeftJuggling(arr, n, d); break; case 4: rotateLeftReversal(arr, n, d); break; default: printf("Invalid method.\n"); continue; } printf("Rotated left by %d: ", d); printArray(arr, n); break; } case 3: performanceComparison(); break; case 4: demonstrateEdgeCases(); break; case 5: printf("Exiting.\n"); return EXIT_SUCCESS; default: printf("Invalid choice. Please try again.\n"); break; } } return EXIT_SUCCESS; } /* Approach 1: Rotate one by one */ void rotateLeftOneByOne(int arr[], int n, int d) { if (n <= 1) return; d %= n; if (d == 0) return; for (int i = 0; i < d; i++) { int first = arr[0]; for (int j = 0; j < n - 1; j++) { arr[j] = arr[j + 1]; } arr[n - 1] = first; } } /* Approach 2: Temporary array */ void rotateLeftTemp(int arr[], int n, int d) { if (n <= 1) return; d %= n; if (d == 0) return; int *temp = malloc(n * sizeof(int)); if (temp == NULL) { fprintf(stderr, "Memory allocation failed.\n"); return; } for (int i = 0; i < n - d; i++) { temp[i] = arr[d + i]; } for (int i = 0; i < d; i++) { temp[n - d + i] = arr[i]; } for (int i = 0; i < n; i++) { arr[i] = temp[i]; } free(temp); } /* Approach 3: Juggling algorithm */ int gcd(int a, int b) { while (b) { int temp = b; b = a % b; a = temp; } return a; } void rotateLeftJuggling(int arr[], int n, int d) { if (n <= 1) return; d %= n; if (d == 0) return; int cycles = gcd(n, d); for (int i = 0; i < cycles; i++) { int currIdx = i; int currEle = arr[currIdx]; do { int nextIdx = (currIdx - d + n) % n; int nextEle = arr[nextIdx]; arr[nextIdx] = currEle; currEle = nextEle; currIdx = nextIdx; } while (currIdx != i); } } /* Approach 4: Reversal algorithm */ void reverse(int arr[], int start, int end) { while (start < end) { int temp = arr[start]; arr[start] = arr[end]; arr[end] = temp; start++; end--; } } void rotateLeftReversal(int arr[], int n, int d) { if (n <= 1) return; d %= n; if (d == 0) return; reverse(arr, 0, d - 1); reverse(arr, d, n - 1); reverse(arr, 0, n - 1); } /* Prints array */ void printArray(const int arr[], int n) { printf("["); for (int i = 0; i < n; i++) { printf("%d", arr[i]); if (i < n - 1) printf(", "); } printf("]\n"); } /* Compares arrays */ int arraysEqual(const int a[], const int b[], int n) { for (int i = 0; i < n; i++) { if (a[i] != b[i]) return 0; } return 1; } /* Copies array */ void copyArray(const int src[], int dst[], int n) { memcpy(dst, src, n * sizeof(int)); } /* Demonstrates all approaches */ void demonstrateApproaches(void) { printf("\n=== All Left Rotation Approaches ===\n"); int original[] = {1, 2, 3, 4, 5, 6}; int n = sizeof(original) / sizeof(original[0]); int d = 2; int expected[] = {3, 4, 5, 6, 1, 2}; int arr[MAX_SIZE]; printf("Original: [1, 2, 3, 4, 5, 6], d = 2\n"); printf("Expected: [3, 4, 5, 6, 1, 2]\n\n"); copyArray(original, arr, n); rotateLeftOneByOne(arr, n, d); printf("One by One: "); printArray(arr, n); printf(" Verify: %s\n", arraysEqual(arr, expected, n) ? "PASS" : "FAIL"); copyArray(original, arr, n); rotateLeftTemp(arr, n, d); printf("Temp Array: "); printArray(arr, n); printf(" Verify: %s\n", arraysEqual(arr, expected, n) ? "PASS" : "FAIL"); copyArray(original, arr, n); rotateLeftJuggling(arr, n, d); printf("Juggling: "); printArray(arr, n); printf(" Verify: %s\n", arraysEqual(arr, expected, n) ? "PASS" : "FAIL"); copyArray(original, arr, n); rotateLeftReversal(arr, n, d); printf("Reversal: "); printArray(arr, n); printf(" Verify: %s\n", arraysEqual(arr, expected, n) ? "PASS" : "FAIL"); } /* Performance comparison */ void performanceComparison(void) { printf("\n=== Performance Comparison (n = 100000, d = 12345) ===\n"); int size = 100000; int d = 12345; int *original = malloc(size * sizeof(int)); int *arr = malloc(size * sizeof(int)); if (original == NULL || arr == NULL) { fprintf(stderr, "Memory allocation failed.\n"); free(original); free(arr); return; } for (int i = 0; i < size; i++) { original[i] = i; } clock_t start, end; double timeTaken; copyArray(original, arr, size); start = clock(); rotateLeftTemp(arr, size, d); end = clock(); timeTaken = ((double)(end - start)) / CLOCKS_PER_SEC * 1000.0; printf("Temp Array: %.3f ms\n", timeTaken); copyArray(original, arr, size); start = clock(); rotateLeftJuggling(arr, size, d); end = clock(); timeTaken = ((double)(end - start)) / CLOCKS_PER_SEC * 1000.0; printf("Juggling: %.3f ms\n", timeTaken); copyArray(original, arr, size); start = clock(); rotateLeftReversal(arr, size, d); end = clock(); timeTaken = ((double)(end - start)) / CLOCKS_PER_SEC * 1000.0; printf("Reversal: %.3f ms\n", timeTaken); free(original); free(arr); } /* Demonstrates edge cases */ void demonstrateEdgeCases(void) { printf("\n=== Edge Cases ===\n"); /* Case 1: d = 0 */ int arr1[] = {1, 2, 3, 4, 5}; printf("Case 1: d = 0 (no rotation)\n"); printf(" Before: "); printArray(arr1, 5); rotateLeftReversal(arr1, 5, 0); printf(" After: "); printArray(arr1, 5); /* Case 2: d > n */ int arr2[] = {1, 2, 3}; printf("\nCase 2: d = 4 > n = 3 (d %% n = 1)\n"); printf(" Before: "); printArray(arr2, 3); rotateLeftReversal(arr2, 3, 4); printf(" After: "); printArray(arr2, 3); /* Case 3: Single element */ int arr3[] = {42}; printf("\nCase 3: Single element\n"); printf(" Before: "); printArray(arr3, 1); rotateLeftReversal(arr3, 1, 3); printf(" After: "); printArray(arr3, 1); /* Case 4: d = n */ int arr4[] = {1, 2, 3, 4}; printf("\nCase 4: d = n (no change)\n"); printf(" Before: "); printArray(arr4, 4); rotateLeftReversal(arr4, 4, 4); printf(" After: "); printArray(arr4, 4); } /* Reads an integer safely */ int readInteger(const char *prompt, int *outValue) { char buffer[MAX_LINE_LEN]; char *endPtr; long val; printf("%s", prompt); fflush(stdout); if (fgets(buffer, sizeof(buffer), stdin) == NULL) { return -1; } errno = 0; val = strtol(buffer, &endPtr, 10); if (endPtr == buffer || (*endPtr != '\n' && *endPtr != '\0')) { return -1; } if (errno == ERANGE || val < -2147483647 - 1 || val > 2147483647) { return -1; } *outValue = (int)val; return 0; }

Explanation of Left Rotation Approaches

1. One by One: Simple, O(n × d) time — inefficient for large d.
2. Temporary Array: O(n) time, O(n) space — simple and fast.
3. Juggling: O(n) time, O(1) space — uses GCD cycles for left rotation.
4. Reversal: O(n) time, O(1) space — reverse first d, then rest, then all.

Expected Output (sample run)

text

=== Array Left Rotation (Counterclockwise) Demo === --- Menu --- 1. Demonstrate All Approaches 2. Custom Rotation 3. Performance Comparison 4. Edge Cases 5. Exit Enter choice: 1 === All Left Rotation Approaches === Original: [1, 2, 3, 4, 5, 6], d = 2 Expected: [3, 4, 5, 6, 1, 2] One by One: [3, 4, 5, 6, 1, 2] Verify: PASS Temp Array: [3, 4, 5, 6, 1, 2] Verify: PASS Juggling: [3, 4, 5, 6, 1, 2] Verify: PASS Reversal: [3, 4, 5, 6, 1, 2] Verify: PASS --- Menu --- ... Enter choice: 3 === Performance Comparison (n = 100000, d = 12345) === Temp Array: 0.812 ms Juggling: 0.598 ms Reversal: 0.561 ms --- Menu --- ... Enter choice: 4 === Edge Cases === Case 1: d = 0 (no rotation) Before: [1, 2, 3, 4, 5] After: [1, 2, 3, 4, 5] Case 2: d = 4 > n = 3 (d % n = 1) Before: [1, 2, 3] After: [2, 3, 1] Case 3: Single element Before: [42] After: [42] Case 4: d = n (no change) Before: [1, 2, 3, 4] After: [1, 2, 3, 4]

---

Common Pitfalls, Edge Cases & Memory Considerations

1. Not Handling d > n

Forgetting d %= n causes incorrect or excessive rotations.

c

void rotate(int arr[], int n, int d) { /* BUG: d might be > n */ }

Solution: Always apply d %= n at the start.

2. Negative d

Negative d causes implementation-defined modulo results.

c

d = -1; d %= n; /* Implementation-defined for negatives */

Solution: Normalize: d = ((d % n) + n) % n;

3. Empty Array

Rotating an empty array with n = 0 causes division by zero.

c

d %= n; /* BUG: n == 0 */

Solution: Check if (n <= 1) return; at the start.

4. Single Element

A single-element array is unchanged by rotation.

Solution: Early return for n <= 1.

5. Memory Leaks with Temporary Array

Forgetting to free the temporary array.

c

int *temp = malloc(n * sizeof(int)); /* ... */ /* Missing free(temp); */

Solution: Always free dynamically allocated memory.

6. Juggling Direction Confusion

For left rotation, the index formula differs from right rotation.

c

/* Right rotation: nextIdx = (currIdx + d) % n */ /* Left rotation: nextIdx = (currIdx - d + n) % n */

Solution: Use the correct formula for the direction.

7. Reversal Order for Left Rotation

The order of reversals differs between left and right rotation.

c

/* Left rotation: reverse first d, reverse rest, reverse all */ /* Right rotation: reverse all, reverse first d, reverse rest */

Solution: Follow the correct order for left rotation.

8. Off-by-One in Reversal Bounds

Incorrect bounds cause elements not to be reversed.

c

reverse(arr, 0, d); /* BUG: should be d - 1 */

Solution: Use reverse(arr, 0, d - 1) for first d elements.

9. Integer Overflow in Index Computation

(currIdx - d + n) % n may overflow for very large n.

Solution: Use (currIdx - (d % n) + n) % n to keep values small.

10. Memory Considerations

• One-by-One: O(1) space, but slow for large d.
• Temporary Array: O(n) space, fast.
• Juggling: O(1) space, optimal for in-place.
• Reversal: O(1) space, simplest in-place.

---

Summary & Best Practices

Left array rotation is a fundamental operation with multiple efficient implementations. The reversal algorithm is the most elegant in-place solution; the temporary array is simplest for readability.

Key Takeaways

• Left rotation by d moves elements left; wrap-around occurs at index 0.
• Apply d %= n to handle d > n.
• One-by-One: O(n × d) time — simple but slow.
• Temporary Array: O(n) time, O(n) space — simple and fast.
• Juggling: O(n) time, O(1) space — uses GCD cycles.
• Reversal: O(n) time, O(1) space — reverse first d, rest, then all.

Best Practices

1. Always apply d %= n to handle d > n.
2. Handle edge cases: empty array, single element, d = 0, d = n.
3. Use the reversal algorithm for in-place O(1) rotation.
4. Use the temporary array for clarity when space permits.
5. Free dynamically allocated memory in temporary array approach.
6. Use the correct index formula for left rotation in juggling.
7. Validate input (array size, d range).
8. Document whether rotation is left or right.
9. Test with odd and even array lengths.
10. Measure performance for very large arrays.

By mastering left array rotation, you’ll have a powerful tool for circular data processing, rotated sorted array problems, and algorithm design.