Reverse an Array in groups of given size
Given an array arr[] and an integer K, the task is to reverse every subarray formed by consecutive K elements.
Examples:
Input: arr[] = [1, 2, 3, 4, 5, 6, 7, 8, 9], K = 3
Output: 3, 2, 1, 6, 5, 4, 9, 8, 7Input: arr[] = [1, 2, 3, 4, 5, 6, 7, 8], K = 5
Output: 5, 4, 3, 2, 1, 8, 7, 6Input: arr[] = [1, 2, 3, 4, 5, 6], K = 1
Output: 1, 2, 3, 4, 5, 6Input: arr[] = [1, 2, 3, 4, 5, 6, 7, 8], K = 10
Output: 8, 7, 6, 5, 4, 3, 2, 1
Naive Approach: The problem can be solved based on the following idea:
Consider every sub-array of size k starting from the beginning of the array and reverse it. We need to handle some special cases.
- If k is not a multiple of n where n is the size of the array, for the last group we will have less than k elements left, we need to reverse all remaining elements.
- If k = 1, the array should remain unchanged. If k >= n, we reverse all elements present in the array.
Follow the below illustration for a better understanding.
Illustration:
Given array arr[] = {1, 2, 3, 4, 5, 6, 7, 8} and k = 3
1st iteration:
- The selected group is {1, 2, 3, 4, 5, 6, 7, 8}
- After swapping the elements we have {3, 2, 1, 4, 5, 6, 7, 8}
2nd iteration:
- The selected group is {3, 2, 1, 4, 5, 6, 7, 8}
- After swapping the elements {3, 2, 1, 6, 5, 4, 7, 8}
3rd iteration:
- As k is less than the count of remaining elements
- We will reverse the entire remaining subarray {3, 2, 1, 6, 5, 4, 8, 7}
Follow the steps mentioned below to implement the idea:
- Iterate over the array, and on each iteration:
- We will set the left pointer as the current index and the right pointer at a distance of group size(K)
- We will swap elements in the left and right indices, and increase left by one and decrease right by one
- Do the above step until left < right
- After the swap operation is done we will increment the value of the iterator by k ( group size )
Below is the implementation of the above approach:
C++
// C++ program to reverse every sub-array formed by // consecutive k elements #include <iostream> using namespace std; // Function to reverse every sub-array formed by // consecutive k elements void reverse( int arr[], int n, int k) { for ( int i = 0; i < n; i += k) { int left = i; // to handle case when k is not multiple of n int right = min(i + k - 1, n - 1); // reverse the sub-array [left, right] while (left < right) swap(arr[left++], arr[right--]); } } // Driver code int main() { int arr[] = {1, 2, 3, 4, 5, 6, 7, 8}; int k = 3; int n = sizeof (arr) / sizeof (arr[0]); reverse(arr, n, k); for ( int i = 0; i < n; i++) cout << arr[i] << " " ; return 0; } |
C
// C program to reverse every sub-array formed by // consecutive k elements #include <stdio.h> // Function to reverse every sub-array formed by // consecutive k elements void reverse( int arr[], int n, int k) { for ( int i = 0; i < n; i += k) { int left = i; int right; // to handle case when k is not multiple of n if (i+k-1<n-1) right = i+k-1; else right = n-1; // reverse the sub-array [left, right] while (left < right) { // swap int temp = arr[left]; arr[left] = arr[right]; arr[right] = temp; left++; right--; } } } // Driver code int main() { int arr[] = {1, 2, 3, 4, 5, 6, 7, 8}; int k = 3; int n = sizeof (arr) / sizeof (arr[0]); reverse(arr, n, k); for ( int i = 0; i < n; i++) printf ( "%d " ,arr[i]); return 0; } // This code is contributed by Arpit Jain |
Java
// Java program to reverse every sub-array formed by // consecutive k elements class GFG { // Function to reverse every sub-array formed by // consecutive k elements static void reverse( int arr[], int n, int k) { for ( int i = 0 ; i < n; i += k) { int left = i; // to handle case when k is not multiple // of n int right = Math.min(i + k - 1 , n - 1 ); int temp; // reverse the sub-array [left, right] while (left < right) { temp=arr[left]; arr[left]=arr[right]; arr[right]=temp; left+= 1 ; right-= 1 ; } } } // Driver method public static void main(String[] args) { int arr[] = { 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 }; int k = 3 ; int n = arr.length; reverse(arr, n, k); for ( int i = 0 ; i < n; i++) System.out.print(arr[i] + " " ); } } // This code is contributed by Anant Agarwal. |
Python3
# Python 3 program to reverse every # sub-array formed by consecutive k # elements # Function to reverse every sub-array # formed by consecutive k elements def reverse(arr, n, k): i = 0 while (i<n): left = i # To handle case when k is not # multiple of n right = min (i + k - 1 , n - 1 ) # Reverse the sub-array [left, right] while (left < right): arr[left], arr[right] = arr[right], arr[left] left + = 1 ; right - = 1 i + = k # Driver code arr = [ 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 ] k = 3 n = len (arr) reverse(arr, n, k) for i in range ( 0 , n): print (arr[i], end = " " ) # This code is contributed by Smitha Dinesh Semwal |
C#
// C# program to reverse every sub-array // formed by consecutive k elements using System; class GFG { // Function to reverse every sub-array // formed by consecutive k elements public static void reverse( int [] arr, int n, int k) { for ( int i = 0; i < n; i += k) { int left = i; // to handle case when k is // not multiple of n int right = Math.Min(i + k - 1, n - 1); int temp; // reverse the sub-array [left, right] while (left < right) { temp = arr[left]; arr[left] = arr[right]; arr[right] = temp; left += 1; right -= 1; } } } // Driver Code public static void Main( string [] args) { int [] arr = new int [] {1, 2, 3, 4, 5, 6, 7, 8}; int k = 3; int n = arr.Length; reverse(arr, n, k); for ( int i = 0; i < n; i++) { Console.Write(arr[i] + " " ); } } } // This code is contributed // by Shrikant13 |
Javascript
<script> // Javascript program to reverse every sub-array // formed by consecutive k elements // Function to reverse every sub-array // formed by consecutive k elements function reverse(arr, n, k) { for (let i = 0; i < n; i += k) { let left = i; // To handle case when k is not // multiple of n let right = Math.min(i + k - 1, n - 1); let temp; // Reverse the sub-array [left, right] while (left < right) { temp = arr[left]; arr[left] = arr[right]; arr[right] = temp; left += 1; right -= 1; } } return arr; } // Driver Code let arr = new Array(1, 2, 3, 4, 5, 6, 7, 8); let k = 3; let n = arr.length; let arr1 = reverse(arr, n, k); for (let i = 0; i < n; i++) document.write(arr1[i] + " " ); // This code is contributed by saurabh jaiswal </script> |
PHP
<?php // PHP program to reverse every sub-array // formed by consecutive k elements // Function to reverse every sub-array // formed by consecutive k elements function reverse( $arr , $n , $k ) { for ( $i = 0; $i < $n ; $i += $k ) { $left = $i ; // to handle case when k is not // multiple of n $right = min( $i + $k - 1, $n - 1); $temp ; // reverse the sub-array [left, right] while ( $left < $right ) { $temp = $arr [ $left ]; $arr [ $left ] = $arr [ $right ]; $arr [ $right ] = $temp ; $left += 1; $right -= 1; } } return $arr ; } // Driver Code $arr = array (1, 2, 3, 4, 5, 6, 7, 8); $k = 3; $n = sizeof( $arr ); $arr1 = reverse( $arr , $n , $k ); for ( $i = 0; $i < $n ; $i ++) echo $arr1 [ $i ] . " " ; // This code is contributed // by Akanksha Rai ?> |
3 2 1 6 5 4 8 7
Time complexity: O(N)
Auxiliary space: O(1)
Using STL:
C++
#include <bits/stdc++.h> using namespace std; // Function to reverse subarrays of size k in an array // Nikunj Sonigara void reverse( int arr[], int n, int k) { int j = 0, i = k; // Reverse subarrays of size k until the end of the array is reached while (i < n) { // Reverse the subarray from arr[j] to arr[i-1] reverse(arr + j, arr + i); // Move to the next subarray of size k i += k; j += k; } // Reverse the remaining subarray of size less than k reverse(arr + j, arr + n); } // Driver code int main() { int arr[] = {1, 2, 3, 4, 5, 6, 7, 8}; int k = 3; int n = sizeof (arr) / sizeof (arr[0]); // Reverse subarrays of size k in the array reverse(arr, n, k); // Print the reversed array for ( int i = 0; i < n; i++) cout << arr[i] << " " ; return 0; } |
Java
import java.util.Arrays; public class ArrayReverse { // Function to reverse subarrays of size k in an array // Nikunj Sonigara public static void reverse( int [] arr, int n, int k) { int j = 0 , i = k; // Reverse subarrays of size k until the end of the array is reached while (i < n) { // Reverse the subarray from arr[j] to arr[i-1] reverseArray(arr, j, i - 1 ); // Move to the next subarray of size k i += k; j += k; } // Reverse the remaining subarray of size less than k reverseArray(arr, j, n - 1 ); } // Function to reverse an array from index start to end private static void reverseArray( int [] arr, int start, int end) { while (start < end) { int temp = arr[start]; arr[start] = arr[end]; arr[end] = temp; start++; end--; } } // Driver code public static void main(String[] args) { int [] arr = { 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 }; int k = 3 ; int n = arr.length; // Reverse subarrays of size k in the array reverse(arr, n, k); // Print the reversed array for ( int i = 0 ; i < n; i++) System.out.print(arr[i] + " " ); } } |
Python3
# Function to reverse subarrays of size k in an array # Nikunj Sonigara def reverse(arr, n, k): j = 0 i = k # Reverse subarrays of size k until the end of the array is reached while i < n: # Reverse the subarray from arr[j] to arr[i-1] reverse_array(arr, j, i - 1 ) # Move to the next subarray of size k i + = k j + = k # Reverse the remaining subarray of size less than k reverse_array(arr, j, n - 1 ) # Function to reverse an array from index start to end def reverse_array(arr, start, end): while start < end: arr[start], arr[end] = arr[end], arr[start] start + = 1 end - = 1 # Driver code if __name__ = = "__main__" : arr = [ 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 ] k = 3 n = len (arr) # Reverse subarrays of size k in the array reverse(arr, n, k) # Print the reversed array print ( * arr) |
C#
using System; public class ArrayReverse { // Function to reverse subarrays of size k in an array // Nikunj Sonigara public static void Reverse( int [] arr, int n, int k) { int j = 0, i = k; // Reverse subarrays of size k until the end of the array is reached while (i < n) { // Reverse the subarray from arr[j] to arr[i-1] ReverseArray(arr, j, i - 1); // Move to the next subarray of size k i += k; j += k; } // Reverse the remaining subarray of size less than k ReverseArray(arr, j, n - 1); } // Function to reverse an array from index start to end private static void ReverseArray( int [] arr, int start, int end) { while (start < end) { int temp = arr[start]; arr[start] = arr[end]; arr[end] = temp; start++; end--; } } // Driver code public static void Main( string [] args) { int [] arr = { 1, 2, 3, 4, 5, 6, 7, 8 }; int k = 3; int n = arr.Length; // Reverse subarrays of size k in the array Reverse(arr, n, k); // Print the reversed array foreach ( int num in arr) Console.Write(num + " " ); } } |
Javascript
// Function to reverse subarrays of size k in an array // Nikunj Sonigara function reverse(arr, n, k) { let j = 0; let i = k; // Reverse subarrays of size k until the end of the array is reached while (i < n) { // Reverse the subarray from arr[j] to arr[i-1] reverseArray(arr, j, i - 1); // Move to the next subarray of size k i += k; j += k; } // Reverse the remaining subarray of size less than k reverseArray(arr, j, n - 1); } // Function to reverse an array from index start to end function reverseArray(arr, start, end) { while (start < end) { [arr[start], arr[end]] = [arr[end], arr[start]]; start++; end--; } } // Driver code const arr = [1, 2, 3, 4, 5, 6, 7, 8]; const k = 3; const n = arr.length; // Reverse subarrays of size k in the array reverse(arr, n, k); // Print the reversed array console.log(arr.join( ' ' )); |
3 2 1 6 5 4 8 7
Time complexity: O(N)
Auxiliary space: O(1)
Contact Us