Given an array arr[] and a position in array, k. Write a function name reverse (a[], k) such that it reverses subarray arr[0..k-1]. Extra space used should be O(1) and time complexity should be O(k). Examples:
Input: arr[] = {1, 2, 3, 4, 5, 6}
k = 4
Output: arr[] = {4, 3, 2, 1, 5, 6}
This problem has existing solution please refer Reverse an array upto a given position link. We will solve this problem quickly in Python.
Python3
# Program to Reverse an array # upto a given position def reverseArrayUptoK(input, k): # reverse list starting from k-1 position # and split remaining list after k # concat both parts and print # input[k-1::-1] --> generate list starting # from k-1 position element till first # element in reverse order print (input[k-1::-1] + input[k:])# Driver programif __name__ == "__main__": input = [1, 2, 3, 4, 5, 6] k = 4 reverseArrayUptoK(input, k) |
Output:
[4, 3, 2, 1, 5, 6]
Method#2: Using Two Pointers
Approach
Reversing an array upto a given position uses two pointers to swap the elements of the array.
Algorithm
1. Take input array and a number k
2. Initialize two pointers, one pointing to the start of the array and the other pointing to the kth index of the array.
3. Swap the elements at the two pointers and increment the first pointer and decrement the second pointer until the two pointers meet or cross each other.
4. Return the modified array.
Python3
def reverseArray(arr, k): start = 0 end = k-1 while start < end: arr[start], arr[end] = arr[end], arr[start] start += 1 end -= 1 return arrarr=[1, 2, 3, 4, 5, 6]k = 4print(reverseArray(arr, k)) |
[4, 3, 2, 1, 5, 6]
Time complexity: O(k/2), which is equivalent to O(k),traverse only the first k/2 elements of the array to swap the elements.
Auxiliary Space: O(1) as we are not using any extra space to store the elements.
Method using NumPy’s flip() function:
note: install numpy module using command “pip install numpy”
Approach:
Using flip() function we can reverse the subarray arr without using any loops. We first create a array from the given input array, and then we use the flip() function to reverse the subarray up to the k-1 position. We then convert the NumPy array back to a Python list and return it.
Algorithm:
Convert the input list to a NumPy array using np.array() function.
Reverse the subarray up to k-1 position using the flip() function.
Convert the NumPy array back to a Python list using the tolist() function.
Return the modified list.
Python3
import numpy as np# function to reverse array upto given positiondef reverseArrayUptoK(arr, k): # reverse subarray upto position k arr[0:k] = np.flip(arr[0:k], axis=0) return arr# driver codeif __name__ == "__main__": arr = [1, 2, 3, 4, 5, 6] k = 4 print(reverseArrayUptoK(arr, k)) |
Output:
[4, 3, 2, 1, 5, 6]
Time Complexity:
The time complexity of this method is O(k) since we are only reversing the subarray up to the k-1 position.
Auxiliary Space:
The space complexity of this method is O(n) since we are creating a NumPy array of size n, where n is the length of the input list.
