Reverse an array in groups of given size | Set 2 (Variations of Set 1 )
Given an array, reverse every sub-array that satisfies the given constraints.
We have discussed a solution where we reverse every sub-array formed by consecutive k elements in Set 1. In this set, we will discuss various interesting variations of this problem.
Variation 1 (Reverse Alternate Groups): Reverse every alternate sub-array formed by consecutive k elements.
Examples:
Input: arr = [1, 2, 3, 4, 5, 6, 7, 8, 9] k = 3 Output: [3, 2, 1, 4, 5, 6, 9, 8, 7] Input: arr = [1, 2, 3, 4, 5, 6, 7, 8] k = 2 Output: [2, 1, 3, 4, 6, 5, 7, 8]
Algorithm:
- Define a function reverse() that takes an integer array arr, its size n, and the size of the sub-arrays k as input
- Traverse the array in multiples of 2k starting from the first element, i.e., for i = 0, 2k, 4k, and so on.
- For each such i, set the left pointer to i and the right pointer to min(i + k – 1, n – 1) to handle the case when 2k is not a multiple of n.
- Reverse the sub-array [left, right] using a while loop and the swap() function.
- Repeat steps 3-4 for every alternate sub-array formed by consecutive k elements.
- In the main function, declare an integer array arr, initialize it with some values, and define the size of the sub-arrays k.
- Determine the size of the array n using the sizeof() operator.
- Call the reverse() function passing the integer array arr, its size n, and the size of the sub-arrays k as input.
- Print the modified array arr.
Below is the implementation :
C++
// C++ program to reverse every alternate sub-array // formed by consecutive k elements #include <iostream> using namespace std; // Function to reverse every alternate sub-array // formed by consecutive k elements void reverse( int arr[], int n, int k) { // increment i in multiples of 2*k for ( int i = 0; i < n; i += 2*k) { int left = i; // to handle case when 2*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, 9, 10, 11, 12, 13, 14}; 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; } |
Java
// Java program to reverse // every alternate sub-array // formed by consecutive k elements class GFG { // Function to reverse every // alternate sub-array formed // by consecutive k elements static void reverse( int arr[], int n, int k) { // increment i in multiples of 2*k for ( int i = 0 ; i < n; i += 2 * k) { int left = i; // to handle case when 2*k is not multiple of n int right = Math.min(i + k - 1 , n - 1 ); // reverse the sub-array [left, right] while (left < right) { swap(arr, left++, right--); } } } static int [] swap( int [] array, int i, int j) { int temp = array[i]; array[i] = array[j]; array[j] = temp; return array; } // Driver code public static void main(String[] args) { int arr[] = { 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 11 , 12 , 13 , 14 }; 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 has been contributed by 29AjayKumar |
Python3
# Python3 program to reverse every alternate sub-array # formed by consecutive k elements # Function to reverse every alternate sub-array # formed by consecutive k elements def reverse(arr, n, k): # increment i in multiples of 2*k for i in range ( 0 ,n, 2 * k): left = i # to handle case when 2*k is not multiple of n right = min (i + k - 1 , n - 1 ) # 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 if __name__ = = '__main__' : arr = [ 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 11 , 12 , 13 , 14 ] k = 3 n = len (arr) reverse(arr, n, k) for i in range ( 0 ,n, 1 ): print (arr[i],end = " " ) # This code is contributed by # Surendra_Gangwar |
C#
// C# program to reverse every alternate // sub-array formed by consecutive k elements using System; class GFG { // Function to reverse every // alternate sub-array formed // by consecutive k elements static void reverse( int []arr, int n, int k) { // increment i in multiples of 2*k for ( int i = 0; i < n; i += 2 * k) { int left = i; // to handle case when 2*k is // not multiple of n int right = Math.Min(i + k - 1, n - 1); // reverse the sub-array [left, right] while (left < right) { swap(arr, left++, right--); } } } static int [] swap( int [] array, int i, int j) { int temp = array[i]; array[i] = array[j]; array[j] = temp; return array; } // Driver code public static void Main(String[] args) { int []arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14}; 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 PrinciRaj1992 |
Javascript
<script> // Javascript program to reverse // every alternate sub-array // formed by consecutive k elements // Function to reverse every // alternate sub-array formed // by consecutive k elements function reverse(arr, n, k) { // Increment i in multiples of 2*k for (let i = 0; i < n; i += 2 * k) { let left = i; // To handle case when 2*k is // not multiple of n let right = Math.min(i + k - 1, n - 1); // reverse the sub-array [left, right] while (left < right) { swap(arr, left++, right--); } } } function swap(array, i, j) { let temp = array[i]; array[i] = array[j]; array[j] = temp; return array; } // Driver code let arr = [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14 ]; let k = 3; let n = arr.length; reverse(arr, n, k); for (let i = 0; i < n; i++) { document.write(arr[i] + " " ); } // This code is contributed by rag2127 </script> |
3 2 1 4 5 6 9 8 7 10 11 12 14 13
Time Complexity: O(N)
Auxiliary Space: O(1)
Variation 2 (Reverse at given distance): Reverse every sub-array formed by consecutive k elements at given distance apart.
Examples:
Input: arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] k = 3 m = 2 Output: [3, 2, 1, 4, 5, 8, 7, 6, 9, 10] Input: arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] k = 3 m = 1 Output: [3, 2, 1, 4, 7, 6, 5, 8, 10, 9] Input: arr = [1, 2, 3, 4, 5, 6, 7, 8] k = 2 m = 0 Output: [2, 1, 4, 3, 6, 5, 8, 7]
Below is its implementation:
C++
// C++ program to reverse every sub-array formed by // consecutive k elements at given distance apart #include <iostream> using namespace std; // Function to reverse every sub-array formed by // consecutive k elements at m distance apart void reverse( int arr[], int n, int k, int m) { // increment i in multiples of k + m for ( int i = 0; i < n; i += k + m) { int left = i; // to handle case when k + m 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, 9, 10, 11, 12, 13, 14}; int k = 3; int m = 2; int n = sizeof (arr) / sizeof (arr[0]); reverse(arr, n, k, m); for ( int i = 0; i < n; i++) cout << arr[i] << " " ; return 0; } |
Java
// java program to reverse every sub-array formed by // consecutive k elements at given distance apart class GFG { // Function to reverse every sub-array formed by // consecutive k elements at m distance apart static void reverse( int [] arr, int n, int k, int m) { // increment i in multiples of k + m for ( int i = 0 ; i < n; i += k + m) { int left = i; // to handle case when k + m is not multiple of n int right = Math.min(i + k - 1 , n - 1 ); // reverse the sub-array [left, right] while (left < right) swap(arr,left++, right--); } } static int [] swap( int [] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; return arr; } // Driver code public static void main(String[] args) { int arr[] = { 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 11 , 12 , 13 , 14 }; int k = 3 ; int m = 2 ; int n = arr.length; reverse(arr, n, k, m ); for ( int i = 0 ; i < n; i++) { System.out.print(arr[i] + " " ); } } } // This code has been contributed by Rajput-Ji |
Python3
# Python3 program to reverse every # sub-array formed by consecutive # k elements at given distance apart # Function to reverse every # sub-array formed by consecutive # k elements at m distance apart def reverse(arr, n, k, m): # increment i in multiples of k + m for i in range ( 0 , n, k + m): left = i; # to handle case when k + m # is not multiple of n right = min (i + k - 1 , n - 1 ); # reverse the sub-array [left, right] while (left < right): arr = swap(arr,left, right); left + = 1 ; right - = 1 ; return arr; def swap(arr, i, j): temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; return arr; # Driver code arr = [ 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 11 , 12 , 13 , 14 ]; k = 3 ; m = 2 ; n = len (arr); arr = reverse(arr, n, k, m ); for i in range ( 0 , n): print (arr[i], end = " " ); # This code is contributed by Rajput-Ji |
C#
// C# program to reverse every sub-array // formed by consecutive k elements at // given distance apart using System; class GFG { // Function to reverse every sub-array // formed by consecutive k elements // at m distance apart static void reverse( int [] arr, int n, int k, int m) { // increment i in multiples of k + m for ( int i = 0; i < n; i += k + m) { int left = i; // to handle case when k + m is // not multiple of n int right = Math.Min(i + k - 1, n - 1); // reverse the sub-array [left, right] while (left < right) swap(arr, left++, right--); } } static int [] swap( int [] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; return arr; } // Driver code public static void Main(String[] args) { int []arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14}; int k = 3; int m = 2; int n = arr.Length; reverse(arr, n, k, m ); for ( int i = 0; i < n; i++) { Console.Write(arr[i] + " " ); } } } // This code is contributed by PrinciRaj1992 |
Javascript
<script> // javascript program to reverse every sub-array formed by // consecutive k elements at given distance apart // Function to reverse every sub-array formed by // consecutive k elements at m distance apart function reverse(arr,n,k,m) { // increment i in multiples of k + m for (let i = 0; i < n; i += k + m) { let left = i; // to handle case when k + m is not multiple of n let right = Math.min(i + k - 1, n - 1); // reverse the sub-array [left, right] while (left < right) swap(arr,left++, right--); } } function swap(arr,i,j) { let temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; return arr; } // Driver code let arr=[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]; let k = 3; let m = 2; let n = arr.length; reverse(arr, n, k, m ); for (let i = 0; i < n; i++) { document.write(arr[i] + " " ); } // This code is contributed by ab2127 </script> |
3 2 1 4 5 8 7 6 9 10 13 12 11 14
Time Complexity: O(N)
Auxiliary Space: O(1)
Variation 3 (Reverse by doubling the group size):
Reverse every sub-array formed by consecutive k elements where k doubles itself with every sub-array.
Examples:
Input: arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15] k = 1 Output: [1], [3, 2], [7, 6, 5, 4], [15, 14, 13, 12, 11, 10, 9, 8]
Below is its implementation:
C++
// C++ program to reverse every sub-array formed by // consecutive k elements where k doubles itself with // every sub-array. #include <iostream> using namespace std; // Function to reverse every sub-array formed by // consecutive k elements where k doubles itself // with every sub-array. void reverse( int arr[], int n, int k) { // increment i in multiples of k where value // of k is doubled with each iteration for ( int i = 0; i < n; i += k/2) { int left = i; // to handle case when number of elements in // last group is less than k int right = min(i + k - 1, n - 1); // reverse the sub-array [left, right] while (left < right) swap(arr[left++], arr[right--]); // double value of k with each iteration k = k*2; } } // Driver code int main() { int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16}; int k = 1; int n = sizeof (arr) / sizeof (arr[0]); reverse(arr, n, k); for ( int i = 0; i < n; i++) cout << arr[i] << " " ; return 0; } |
Java
// Java program to reverse every sub-array // formed by consecutive k elements where // k doubles itself with every sub-array. import java.util.*; class GFG { // Function to reverse every sub-array formed by // consecutive k elements where k doubles itself // with every sub-array. static void reverse( int arr[], int n, int k) { // increment i in multiples of k where value // of k is doubled with each iteration for ( int i = 0 ; i < n; i += k / 2 ) { int left = i; // to handle case when number of elements in // last group is less than k int right = Math.min(i + k - 1 , n - 1 ); // reverse the sub-array [left, right] while (left < right) swap(arr, left++, right--); // double value of k with each iteration k = k * 2 ; } } static int [] swap( int [] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; return arr; } // Driver code public static void main(String[] args) { int arr[] = { 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 11 , 12 , 13 , 14 , 15 , 16 }; int k = 1 ; 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 29AjayKumar |
Python3
# Python3 program to reverse every # sub-array formed by consecutive # k elements where k doubles itself # with every sub-array # Function to reverse every sub-array # formed by consecutive k elements # where k doubles itself with every # sub-array def reverse(arr, n, k): i = 0 # Increment i in multiples of k where # value of k is doubled with each # iteration while (i < n): left = i # To handle case when number of elements # in last group is less than k 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 # Double value of k with each iteration k = k * 2 i + = int (k / 2 ) # Driver code arr = [ 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 11 , 12 , 13 , 14 , 15 , 16 ] k = 1 n = len (arr) reverse(arr, n, k) print ( * arr, sep = ' ' ) # This code is contributed by avanitrachhadiya2155 |
C#
// C# program to reverse every sub-array // formed by consecutive k elements where // k doubles itself with every sub-array. using System; class GFG { // Function to reverse every sub-array formed by // consecutive k elements where k doubles itself // with every sub-array. static void reverse( int []arr, int n, int k) { // increment i in multiples of k where value // of k is doubled with each iteration for ( int i = 0; i < n; i += k / 2) { int left = i; // to handle case when number of elements in // last group is less than k int right = Math.Min(i + k - 1, n - 1); // reverse the sub-array [left, right] while (left < right) swap(arr, left++, right--); // double value of k with each iteration k = k * 2; } } static int [] swap( int [] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; return arr; } // Driver code public static void Main(String[] args) { int []arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16}; int k = 1; int n = arr.Length; reverse(arr, n, k); for ( int i = 0; i < n; i++) Console.Write(arr[i] + " " ); } } // This code is contributed by Rajput-Ji |
Javascript
<script> // Javascript program to reverse every sub-array // formed by consecutive k elements where // k doubles itself with every sub-array. // Function to reverse every sub-array formed by // consecutive k elements where k doubles itself // with every sub-array. function reverse(arr,n,k) { // increment i in multiples of k where value // of k is doubled with each iteration for (let i = 0; i < n; i += k / 2) { let left = i; // to handle case when number of elements in // last group is less than k let right = Math.min(i + k - 1, n - 1); // reverse the sub-array [left, right] while (left < right) swap(arr, left++, right--); // double value of k with each iteration k = k * 2; } } function swap(arr,i,j) { let temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; return arr; } // Driver code let arr=[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]; let k = 1; let n = arr.length; reverse(arr, n, k); document.write(arr.join( " " )); // This code is contributed by unknown2108 </script> |
1 3 2 7 6 5 4 15 14 13 12 11 10 9 8 16
Time complexity of all solutions discussed above is O(n).
Auxiliary space used by the program is O(1).