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 elementsvoid 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 codeint 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 elementsvoid 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 codeint 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 elementsclass 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 elementsdef 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 codearr = [1, 2, 3, 4, 5, 6, 7, 8] k = 3n = 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 elementsusing System;class GFG{// Function to reverse every sub-array // formed by consecutive k elementspublic 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 Codepublic 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 elementsfunction 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 Codelet 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 elementsfunction 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?> |
Output
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 Sonigaravoid 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 codeint 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 Sonigaradef 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 enddef reverse_array(arr, start, end): while start < end: arr[start], arr[end] = arr[end], arr[start] start += 1 end -= 1# Driver codeif __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 Sonigarafunction 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 endfunction reverseArray(arr, start, end) { while (start < end) { [arr[start], arr[end]] = [arr[end], arr[start]]; start++; end--; }}// Driver codeconst arr = [1, 2, 3, 4, 5, 6, 7, 8];const k = 3;const n = arr.length;// Reverse subarrays of size k in the arrayreverse(arr, n, k);// Print the reversed arrayconsole.log(arr.join(' ')); |
Output
3 2 1 6 5 4 8 7
Time complexity: O(N)
Auxiliary space: O(1)
This article is contributed by Aditya Goel. If you like neveropen and would like to contribute, you can also write an article using write.neveropen.co.za or mail your article to review-team@neveropen.co.za. See your article appearing on the neveropen main page and help other Geeks.
Please write comments if you find anything incorrect, or if you want to share more information about the topic discussed above.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
