Example:
Input: Given array: [1, 2, 3, 4, 5, 6] Number of rotations: 2 Output: [3, 4, 5, 6, 1, 2]
Explanation:
The array [1, 2, 3, 4, 5, 6] is rotated twice to the left. In each rotation, the elements shift to the left by two positions. After the first rotation, the array becomes [2, 3, 4, 5, 6, 1]. After the second rotation, it becomes [3, 4, 5, 6, 1, 2].
 |
| Left Rotation of an Array |
Python Program to Left Rotation Using Brute Force Approach.
The simplest approach to left-rotate an array is to perform one rotation at a time for the specified number of positions.
Brute Force Algorithm:
- This Algorithm involves an outer loop that runs K times to perform the specified number of rotations.
-
Inside each iteration of the loop, the following steps are executed
to perform a single left rotation:
- Store the first element of the array in a temporary variable to prevent its value from being overwritten.
- Shift all other elements one position to the left. This is done by iterating through the array and assigning each element the value of the element at the next index.
- Place the temporary variable (the original first element) at the end of the array, effectively completing one left rotation.
- This process of rotating the array K times is repeated for the specified number of rotations.
Example Illustration:
Python Code:
# Python code to left rotate array (Brute Force) def left_rotate_array(arr, k): length = len(arr) for i in range(k): # store the first element temp = arr[0] # Shift all other elements to the left for i in range(length - 1): arr[i] = arr[i + 1] # Place the first element at the end arr[length - 1] = temp # Example usage: given_array = [1, 2, 3, 4, 5] rotations = 2 print("Original array:", given_array) left_rotate_array(given_array, rotations) print(f"After {rotations} left rotations:", given_array)
Original array: [1, 2, 3, 4, 5]
After 2 left rotations: [3, 4, 5, 1, 2]- Time Complexity: O(n * d) where n is the length of the array and d is the number of positions to rotate. This can be inefficient for large arrays or a high number of rotations.
- Space Complexity: O(1) no extra space is required to rotate the array using this method.
Python Program to Rotate an Array Using Slicing.
The array left rotation algorithm using slicing in Python involves manipulating the original array to create a left-rotated version without individually moving each element.
Algorithm Explanation:
To handle scenarios where the number of rotations ('k') exceeds the array's length, take the modulo of 'k' with the array's length. This step ensures that 'k' remains within the range of the array's length.
- Create a new list called rotated_array by using Python's list slicing.
- Slice the original array (arr) from index 'k' to the end (arr[k:]). This extracts the elements that need to be moved to the beginning after rotation.
- Concatenate (+) this slice with the portion of the array from the start to index 'k' (arr[:k]). This captures the elements that should be moved to the end after rotation.
- This combination represents the left-rotated version of the array.
- Update the original array (arr) with the values from the rotated_array.
- Iterate through the rotated_array and assign each value to the corresponding index in the original array.
- This step replaces the elements in the original array with the left-rotated elements.
Example Illustration:
This slicing approach efficiently handles left rotation without individually moving each element, making it a concise and Pythonic way to achieve the desired rotation.
Python Code:
def left_rotate_array(arr, k): length = len(arr) k = k % length # Ensure k is within array length # Slicing to perform left rotation rotated_array = arr[k:] + arr[:k] # Update original array with rotated values for i in range(length): arr[i] = rotated_array[i] # Example usage: given_array = [1, 2, 3, 4, 5] rotations = 2 print("Original array:", given_array) left_rotate_array(given_array, rotations) print(f"After {rotations} left rotations:", given_array)
Original array: [1, 2, 3, 4, 5]
After 2 left rotations: [3, 4, 5, 1, 2]- Time Complexity: Slicing in Python takes (n) time complexity, where n is the number of elements being sliced and concatenated.
- Space Complexity: O(n) because we have created a temporary array for rotation.
Python Program to Rotate an Array Using Reversal Algorithm.
The reversal algorithm involves three steps to perform left rotation on an array.
Reversal Algorithm:
- Reverse the elements from the start of the array up to the k index.
- Reverse the elements from the k index to the end of the array.
- Reverse the entire array to obtain the final left-rotated array.
Example Illustration:
def reverse_array(arr, start, end): while start < end: arr[start], arr[end] = arr[end], arr[start] start += 1 end -= 1 def left_rotate_array(arr, k): length = len(arr) k = k % length # Ensure k is within array length for multiple rotations # Reverse the first part: from start to k reverse_array(arr, 0, k - 1) # Reverse the second part: from k to end reverse_array(arr, k, length - 1) # Reverse the entire array reverse_array(arr, 0, length - 1) # Example usage: given_array = [1, 2, 3, 4, 5] rotations = 2 print("Original array:", given_array) left_rotate_array(given_array, rotations) print(f"After {rotations} left rotations:", given_array)
Output:
Original array: [1, 2, 3, 4, 5]
After 2 left rotations: [3, 4, 5, 1, 2]- Time Complexity: For each reversal operation it will take O(n) time so the overall time complexity will be O(n) where n is the number of elements.
- Space Complexity: The algorithm uses a constant amount of extra space O(1).
So these are a few approaches to left-rotate an array in Python. Each approach has different space and time complexity so you can choose the most optimized one for your solution.
No comments:
Post a Comment