Tag O(n) rearrangement

Rearrange Array Such That Even Positioned Are Greater Than Odd in C: A Comprehensive Tutorial

Given an array, the task is to rearrange its elements so that for every even position (1-based), the element is greater than or equal to the previous element, and for every odd position, the element is less than or equal to the previous element. This problem tests your understanding of array manipulation, sorting, and in-place rearrangement.

This tutorial provides an in-depth exploration of rearranging an array with the even-positioned-greater-than-odd condition: the sort-based approach, the single-pass swap approach, practical implementation, common pitfalls, and best practices.

---

Conceptual Introduction & Fundamentals

What is the Problem?

Given an array arr[], rearrange it (using 1-based indexing) such that:

• For every even index i: arr[i] >= arr[i-1]
• For every odd index i: arr[i] <= arr[i-1]

Example:

text

Input: [1, 2, 2, 1] Output: [1, 2, 1, 2] Check (1-based): i=2 (even): arr[2]=2 >= arr[1]=1 ✓ i=3 (odd): arr[3]=1 <= arr[2]=2 ✓ i=4 (even): arr[4]=2 >= arr[3]=1 ✓

Why This Problem Matters

• Array rearrangement: Common in sorting and partitioning problems.
• Local swap technique: Demonstrates single-pass in-place transformations.
• Sort-based reasoning: Shows how ordering simplifies constraints.
• Interview preparation: Common coding interview question.
• Pattern recognition: Teaches alternating peak-valley patterns.

Understanding the Pattern

The resulting array follows a zigzag pattern:

• Odd positions hold smaller values (valleys).
• Even positions hold larger values (peaks).

text

Index (1-based): 1 2 3 4 5 6 Pattern: low high low high low high

Approaches Overview

Approach	Time Complexity	Space Complexity
Sort + assign max to even	O(n log n)	O(n)
Single-pass swap	O(n)	O(1)

---

Syntax & Core Mechanics

Approach 1: Sort and Assign Max to Even Positions

Sort the array, then assign the largest n/2 elements to even positions and the remaining to odd positions.

c

#include <stdio.h> #include <stdlib.h> int compareInts(const void *a, const void *b) { int int_a = *(const int *)a; int int_b = *(const int *)b; return (int_a > int_b) - (int_a < int_b); } void rearrangeArraySort(int arr[], int n) { if (n <= 1) return; /* Sort array in ascending order */ qsort(arr, n, sizeof(int), compareInts); /* Create result array */ int *result = malloc(n * sizeof(int)); if (result == NULL) { fprintf(stderr, "Memory allocation failed.\n"); return; } int ptr1 = 0; /* Points to smallest available */ int ptr2 = n - 1; /* Points to largest available */ for (int i = 0; i < n; i++) { /* i is 0-based; (i+1) is 1-based index */ if ((i + 1) % 2 == 0) { /* Even position: assign largest */ result[i] = arr[ptr2--]; } else { /* Odd position: assign smallest */ result[i] = arr[ptr1++]; } } /* Copy back to original array */ for (int i = 0; i < n; i++) { arr[i] = result[i]; } free(result); } int main(void) { int arr[] = {1, 2, 2, 1}; int n = sizeof(arr) / sizeof(arr[0]); rearrangeArraySort(arr, n); for (int i = 0; i < n; i++) { printf("%d ", arr[i]); } printf("\n"); return 0; }

Expected output:

text

1 2 1 2

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

Approach 2: Single-Pass Swap (In-Place)

Traverse the array once and swap adjacent elements when the condition is violated.

Rules (1-based):

• At even index i: if arr[i] < arr[i-1], swap them.
• At odd index i: if arr[i] > arr[i-1], swap them.

c

#include <stdio.h> void swap(int *a, int *b) { int temp = *a; *a = *b; *b = temp; } void rearrangeArraySwap(int arr[], int n) { if (n <= 1) return; for (int i = 1; i < n; i++) { /* i is 0-based; (i+1) is 1-based index */ if ((i + 1) % 2 == 0) { /* Even position (1-based): ensure arr[i] >= arr[i-1] */ if (arr[i] < arr[i - 1]) { swap(&arr[i], &arr[i - 1]); } } else { /* Odd position (1-based): ensure arr[i] <= arr[i-1] */ if (arr[i] > arr[i - 1]) { swap(&arr[i], &arr[i - 1]); } } } } int main(void) { int arr[] = {1, 2, 2, 1}; int n = sizeof(arr) / sizeof(arr[0]); rearrangeArraySwap(arr, n); for (int i = 0; i < n; i++) { printf("%d ", arr[i]); } printf("\n"); return 0; }

Expected output:

text

1 2 1 2

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

Step-by-Step Trace for [1, 2, 2, 1]

text

Initial: [1, 2, 2, 1] i = 1 (1-based i+1 = 2, even): arr[1]=2 >= arr[0]=1 → OK i = 2 (1-based i+1 = 3, odd): arr[2]=2 > arr[1]=2? No (equal) → OK i = 3 (1-based i+1 = 4, even): arr[3]=1 < arr[2]=2 → swap Array: [1, 2, 1, 2] Final: [1, 2, 1, 2] ✓

---

Full Practical Code Example with Explanation

This program demonstrates both approaches with verification, performance comparison, and edge cases.

Program: Rearrange Array Even-Positioned Greater

c

/** * rearrange_even_greater.c * Rearranges array so even positions (1-based) are >= previous. * Compares sort-based and single-pass swap approaches. */ #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 */ int compareInts(const void *a, const void *b); void rearrangeSort(int arr[], int n); void rearrangeSwap(int arr[], int n); void swap(int *a, int *b); int verifyArrangement(const int arr[], int n); int readInteger(const char *prompt, int *outValue); void printArray(const int arr[], int n); 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("=== Rearrange Array (Even Positioned Greater) ===\n"); while (1) { printf("\n--- Menu ---\n"); printf("1. Demonstrate All Approaches\n"); printf("2. Custom Array\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; 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; } } printf("\nOriginal: "); printArray(arr, n); int *copy = malloc(n * sizeof(int)); if (copy == NULL) break; copyArray(arr, copy, n); rearrangeSort(copy, n); printf("Sort approach: "); printArray(copy, n); printf(" Verify: %s\n", verifyArrangement(copy, n) ? "PASS" : "FAIL"); copyArray(arr, copy, n); rearrangeSwap(copy, n); printf("Swap approach: "); printArray(copy, n); printf(" Verify: %s\n", verifyArrangement(copy, n) ? "PASS" : "FAIL"); free(copy); 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; } /* Comparison function for qsort */ int compareInts(const void *a, const void *b) { int int_a = *(const int *)a; int int_b = *(const int *)b; return (int_a > int_b) - (int_a < int_b); } /* Sort-based approach */ void rearrangeSort(int arr[], int n) { if (n <= 1) return; qsort(arr, n, sizeof(int), compareInts); int *result = malloc(n * sizeof(int)); if (result == NULL) { fprintf(stderr, "Memory allocation failed.\n"); return; } int ptr1 = 0; int ptr2 = n - 1; for (int i = 0; i < n; i++) { if ((i + 1) % 2 == 0) { result[i] = arr[ptr2--]; /* Even position: largest */ } else { result[i] = arr[ptr1++]; /* Odd position: smallest */ } } for (int i = 0; i < n; i++) { arr[i] = result[i]; } free(result); } /* Swap helper */ void swap(int *a, int *b) { int temp = *a; *a = *b; *b = temp; } /* Single-pass swap approach */ void rearrangeSwap(int arr[], int n) { if (n <= 1) return; for (int i = 1; i < n; i++) { if ((i + 1) % 2 == 0) { /* Even position (1-based): ensure arr[i] >= arr[i-1] */ if (arr[i] < arr[i - 1]) { swap(&arr[i], &arr[i - 1]); } } else { /* Odd position (1-based): ensure arr[i] <= arr[i-1] */ if (arr[i] > arr[i - 1]) { swap(&arr[i], &arr[i - 1]); } } } } /* Verifies the arrangement condition */ int verifyArrangement(const int arr[], int n) { for (int i = 1; i < n; i++) { if ((i + 1) % 2 == 0) { /* Even position (1-based): arr[i] >= arr[i-1] */ if (arr[i] < arr[i - 1]) return 0; } else { /* Odd position (1-based): arr[i] <= arr[i-1] */ if (arr[i] > arr[i - 1]) return 0; } } return 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 both approaches */ void demonstrateApproaches(void) { printf("\n=== Sample Arrays ===\n"); int arr1[] = {1, 2, 2, 1}; int n1 = sizeof(arr1) / sizeof(arr1[0]); int copy1[MAX_SIZE]; printf("\nArray 1: "); printArray(arr1, n1); copyArray(arr1, copy1, n1); rearrangeSort(copy1, n1); printf(" Sort: "); printArray(copy1, n1); copyArray(arr1, copy1, n1); rearrangeSwap(copy1, n1); printf(" Swap: "); printArray(copy1, n1); int arr2[] = {1, 3, 2}; int n2 = sizeof(arr2) / sizeof(arr2[0]); printf("\nArray 2: "); printArray(arr2, n2); copyArray(arr2, copy1, n2); rearrangeSort(copy1, n2); printf(" Sort: "); printArray(copy1, n2); copyArray(arr2, copy1, n2); rearrangeSwap(copy1, n2); printf(" Swap: "); printArray(copy1, n2); int arr3[] = {10, 5, 8, 3, 7, 2}; int n3 = sizeof(arr3) / sizeof(arr3[0]); printf("\nArray 3: "); printArray(arr3, n3); copyArray(arr3, copy1, n3); rearrangeSort(copy1, n3); printf(" Sort: "); printArray(copy1, n3); copyArray(arr3, copy1, n3); rearrangeSwap(copy1, n3); printf(" Swap: "); printArray(copy1, n3); int arr4[] = {5, 5, 5, 5, 5}; int n4 = sizeof(arr4) / sizeof(arr4[0]); printf("\nArray 4 (all same): "); printArray(arr4, n4); copyArray(arr4, copy1, n4); rearrangeSwap(copy1, n4); printf(" Swap: "); printArray(copy1, n4); } /* Performance comparison */ void performanceComparison(void) { printf("\n=== Performance Comparison (n = 100000) ===\n"); int n = 100000; int *original = malloc(n * sizeof(int)); int *arr = malloc(n * sizeof(int)); if (original == NULL || arr == NULL) { fprintf(stderr, "Memory allocation failed.\n"); free(original); free(arr); return; } srand(42); for (int i = 0; i < n; i++) { original[i] = rand() % 10000; } clock_t start, end; double timeTaken; /* Sort approach */ copyArray(original, arr, n); start = clock(); rearrangeSort(arr, n); end = clock(); timeTaken = ((double)(end - start)) / CLOCKS_PER_SEC * 1000.0; printf("Sort approach: %.3f ms\n", timeTaken); /* Swap approach */ copyArray(original, arr, n); start = clock(); rearrangeSwap(arr, n); end = clock(); timeTaken = ((double)(end - start)) / CLOCKS_PER_SEC * 1000.0; printf("Swap approach: %.3f ms\n", timeTaken); free(original); free(arr); } /* Demonstrates edge cases */ void demonstrateEdgeCases(void) { printf("\n=== Edge Cases ===\n"); /* Case 1: Single element */ int arr1[] = {42}; printf("Case 1: Single element\n"); printf(" Array: "); printArray(arr1, 1); rearrangeSwap(arr1, 1); printf(" After: "); printArray(arr1, 1); /* Case 2: Two elements */ int arr2[] = {5, 3}; printf("\nCase 2: Two elements\n"); printf(" Array: "); printArray(arr2, 2); rearrangeSwap(arr2, 2); printf(" After: "); printArray(arr2, 2); /* Case 3: Already satisfies condition */ int arr3[] = {1, 3, 2, 5, 4}; printf("\nCase 3: Already satisfies\n"); printf(" Array: "); printArray(arr3, 5); printf(" Verify before: %s\n", verifyArrangement(arr3, 5) ? "PASS" : "FAIL"); rearrangeSwap(arr3, 5); printf(" After: "); printArray(arr3, 5); printf(" Verify after: %s\n", verifyArrangement(arr3, 5) ? "PASS" : "FAIL"); /* Case 4: Decreasing array */ int arr4[] = {5, 4, 3, 2, 1}; printf("\nCase 4: Decreasing array\n"); printf(" Array: "); printArray(arr4, 5); rearrangeSwap(arr4, 5); printf(" After: "); printArray(arr4, 5); printf(" Verify: %s\n", verifyArrangement(arr4, 5) ? "PASS" : "FAIL"); /* Case 5: Increasing array */ int arr5[] = {1, 2, 3, 4, 5}; printf("\nCase 5: Increasing array\n"); printf(" Array: "); printArray(arr5, 5); rearrangeSwap(arr5, 5); printf(" After: "); printArray(arr5, 5); printf(" Verify: %s\n", verifyArrangement(arr5, 5) ? "PASS" : "FAIL"); /* Case 6: All same */ int arr6[] = {7, 7, 7, 7}; printf("\nCase 6: All same\n"); printf(" Array: "); printArray(arr6, 4); rearrangeSwap(arr6, 4); printf(" After: "); printArray(arr6, 4); printf(" Verify: %s\n", verifyArrangement(arr6, 4) ? "PASS" : "FAIL"); /* Case 7: Negative values */ int arr7[] = {-1, -2, -3, -4, -5}; printf("\nCase 7: Negative values\n"); printf(" Array: "); printArray(arr7, 5); rearrangeSwap(arr7, 5); printf(" After: "); printArray(arr7, 5); printf(" Verify: %s\n", verifyArrangement(arr7, 5) ? "PASS" : "FAIL"); } /* 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 Approaches

1. Sort + Assign: Sort array, assign largest to even positions, smallest to odd. O(n log n).
2. Single-Pass Swap: Traverse once, swapping adjacent elements when condition is violated. O(n).

Expected Output (sample run)

text

=== Rearrange Array (Even Positioned Greater) === --- Menu --- 1. Demonstrate All Approaches 2. Custom Array 3. Performance Comparison 4. Edge Cases 5. Exit Enter choice: 1 === Sample Arrays === Array 1: [1, 2, 2, 1] Sort: [1, 2, 1, 2] Swap: [1, 2, 1, 2] Array 2: [1, 3, 2] Sort: [1, 3, 2] Swap: [1, 3, 2] Array 3: [10, 5, 8, 3, 7, 2] Sort: [2, 10, 3, 8, 5, 7] Swap: [5, 10, 3, 8, 2, 7] Array 4 (all same): [5, 5, 5, 5, 5] Swap: [5, 5, 5, 5, 5] --- Menu --- ... Enter choice: 3 === Performance Comparison (n = 100000) === Sort approach: 12.456 ms Swap approach: 0.512 ms --- Menu --- ... Enter choice: 4 === Edge Cases === Case 1: Single element Array: [42] After: [42] Case 2: Two elements Array: [5, 3] After: [3, 5] Case 3: Already satisfies Array: [1, 3, 2, 5, 4] Verify before: PASS After: [1, 3, 2, 5, 4] Verify after: PASS Case 4: Decreasing array Array: [5, 4, 3, 2, 1] After: [4, 5, 2, 3, 1] Verify: PASS Case 5: Increasing array Array: [1, 2, 3, 4, 5] After: [1, 3, 2, 5, 4] Verify: PASS Case 6: All same Array: [7, 7, 7, 7] After: [7, 7, 7, 7] Verify: PASS Case 7: Negative values Array: [-1, -2, -3, -4, -5] After: [-2, -1, -4, -3, -5] Verify: PASS

---

Common Pitfalls, Edge Cases & Memory Considerations

1. Confusing 0-Based and 1-Based Indexing

The problem uses 1-based indexing. In C, arrays are 0-based.

c

/* i is 0-based; (i+1) is 1-based */ if ((i + 1) % 2 == 0) { /* even 1-based position */ }

Solution: Always convert: (i + 1) % 2 == 0 for even 1-based positions.

2. Wrong Swap Direction

Swapping in the wrong direction violates the condition.

c

/* Even 1-based position: ensure arr[i] >= arr[i-1] */ if (arr[i] < arr[i - 1]) swap(&arr[i], &arr[i-1]); /* Odd 1-based position: ensure arr[i] <= arr[i-1] */ if (arr[i] > arr[i - 1]) swap(&arr[i], &arr[i-1]);

3. Single Element

No swaps needed for n = 1.

c

if (n <= 1) return;

4. Two Elements

For n = 2, only the even position (1-based) matters.

c

int arr[] = {5, 3}; /* After swap: [3, 5] (arr[1] >= arr[0]) */

5. Equal Elements

Equality satisfies both >= and <=.

c

int arr[] = {5, 5, 5}; /* Already satisfies condition */

6. Memory Leaks in Sort Approach

Forgetting to free the result array.

c

free(result); /* Required */

7. Sort Stability

qsort is not stable, but this problem doesn’t require stability.

8. Integer Overflow in Comparisons

Comparisons of int values are safe; no overflow.

9. Performance for Large Arrays

Sort approach is O(n log n); swap approach is O(n) — prefer swap for performance.

10. Memory Considerations

• Sort approach: O(n) extra space.
• Swap approach: O(1) extra space.
• Swap approach is preferred for memory and time efficiency.

---

Summary & Best Practices

Rearranging an array so even positions are greater than odd is elegantly solved by the single-pass swap approach in O(n) time and O(1) space. The sort-based approach provides an alternative but uses O(n) extra space and O(n log n) time.

Key Takeaways

• Resulting array follows a zigzag (peak-valley) pattern.
• Even 1-based positions hold larger values.
• Odd 1-based positions hold smaller values.
• Sort approach: O(n log n) time, O(n) space.
• Swap approach: O(n) time, O(1) space — preferred.
• Use (i + 1) % 2 == 0 for even 1-based positions.

Best Practices

1. Use the single-pass swap approach for O(n) time and O(1) space.
2. Use (i + 1) % 2 == 0 to check even 1-based positions.
3. Handle edge cases: single element, all same, negative values.
4. Free dynamically allocated memory in the sort approach.
5. Verify the arrangement after rearrangement.
6. Document the indexing convention (1-based) in comments.
7. Test with increasing, decreasing, and random arrays.
8. Use size_t for array sizes where appropriate.
9. Avoid unnecessary sorting when O(n) suffices.
10. Profile performance for large arrays.

By mastering this problem, you’ll understand local swap techniques and be prepared for related array rearrangement problems.