Reverse every consecutive m-elements of a subarray

By | November 17, 2021 Problem

Given an array, reverse every sub-array formed by consecutive m elements.

Sample Input

[1, 2, 3, 4]     m = 3

[3, 2, 1, 4]

Approach

We can initially place a pointer i at  (m-1)th index of the array to reverse the first m elements’ subarray by traversing floor(m/2) times backwards. After performing this, we can increment i by m and perform a similar task on remaining subarrays.

Note that if size of the array is not divisible by m, then we will need to separately reverse remainder (n % m) elements. This approach takes O(N) time and O(1) auxiliary space.

C++ Programming

#include<bits/stdc++.h>
using namespace std;

// function to reverse in groups
void reverseInGroups(int arr[], int n, int m){
int i=m-1;
while(i<n){
int l2 = i;
int l1 = i-(m-1);
for(int count=1;count<=(m/2);count++){
//traverse subarray backwards and swap elements
swap(arr[l2],arr[l1]);
l1++;
l2--;
}
i+=m;
}
int rem = n%m;    //handle remaining elements
int l2 = n-1;
int l1 = l2 - (rem-1);
for(int count=1;count<=(rem/2);count++){
swap(arr[l2], arr[l1]);
l2--;
l1++;
}
}
int main(){
int arr = {1, 2, 3, 4, 5};
int m = 3;
reverseInGroups(arr, 5, m);
for(int i=0; i<5; i++) cout<<arr[i]<<" ";
}

Output

3 2 1 5 4

C Programming

#include<stdio.h>

// function to reverse array in groups
void reverseInGroups(int arr[], int n, int m){
int i=m-1;
while(i<n){
int l2 = i;
int l1 = i-(m-1);
for(int count=1;count<=(m/2);count++){
//traverse subarray backwards and swap elements
int temp = arr[l1];
arr[l1] = arr[l2];
arr[l2] = temp;
l1++;
l2--;
}
i+=m;
}
int rem = n%m;    //handle remainder elements
int l2 = n-1;
int l1 = l2 - (rem-1);
for(int count=1;count<=(rem/2);count++){
int temp = arr[l1];
arr[l1] = arr[l2];
arr[l2] = temp;
l2--;
l1++;
}
}
void main(){
int arr = {1, 2, 3, 4, 5};
int m = 3;
reverseInGroups(arr, 5, m);
for(int i=0; i<5; i++) printf("%d ",arr[i]);
}

Output

3 2 1 5 4

Another way to code the same algorithm in Python

# Function to reverseArray array in groups
def reverseArray(arr, n, k):
i = 0

while(i<n):

left = i
right = min(i + k - 1, n - 1)

# Reverse the sub-array
while (left < right):

arr[left], arr[right] = arr[right], arr[left]
left+= 1;
right-=1
i+= k

arr = [1, 2, 3, 4, 5]

k = 3
n = len(arr)
reverseArray(arr, n, k)

for i in range(0, n):
print(arr[i], end =" ")

Output

3 2 1 5 4 