Python Program to Reverse Array Using Recursion and While Loop

Hi everyone! In this article, we’ll guide you through the Python program to reverse an array using recursion and while loop. So, let’s get started with the [Problem Link].

Examples of the Python Program to Reverse Array Using Recursion and While Loop:

Example 1:

  Input: arr[] = [1, 2, 3, 4, 5, 6, 7] and L = 2 and R = 4
  Output: [1, 4, 3, 2, 5, 6, 7]
  Explanation: After reversing the elements in range 2 to 4 (2, 3, 4), modified array is 1, 4, 3, 2, 5, 6, 7.

Example 2:

  Input: arr[] = [1, 6, 7, 4] and L = 1 and R = 4
  Output: [4, 7, 6, 1]
  Explanation: After reversing the elements in range 1 to 4 (1, 6, 7, 4), modified array is 4, 7, 6, 1.

Points to Keep in Mind:

Expected Time Complexity: O(n)

Expected Auxiliary Space: O(1)

Constraints:

• 1 ≤ arr.size() ≤ 10⁶
• 1 ≤ arr[i] ≤ 10⁶
• 1 ≤ L ≤ R ≤ arr.size()

1.RECURSION SOLUTION

Problem Statement:

Given:

• An array of integers “arr”
• Two integers “l” and “r”, representing the starting and ending indices (1-based) of a subarray within “arr”

Task:

• Reverse the elements of the subarray from index “l” to index “r” in-place
• Return the modified array after the reversal

Constraints:

• 1 <= l <= r <= len(arr)
• 1 <= len(arr) <= 10^5
• -10^9 <= arr[i] <= 10^9

Examples:

Example 1:

  Input: arr = [1, 2, 3, 4, 5], l = 2, r = 4
  Output: [1, 4, 3, 2, 5]
  Explanation: The subarray from index 2 to 4 is [2, 3, 4]. Reversing it results in [4, 3, 2], so the entire array becomes [1, 4, 3, 2, 5].

Example 2:

  Input: arr = [10, 20, 30, 40, 50], l = 1, r = 5
  Output: [50, 40, 30, 20, 10]
  Explanation: Reversing the entire array.

Example 3:

  Input: arr = [5, 4, 3, 2, 1], l = 3, r = 3
  Output: [5, 4, 3, 2, 1]
  Explanation: Reversing a single element doesn't change the array.

Intuition and Approach:

Objective: Efficiently reverse a specified portion of an array in-place without using additional memory for another array.

Key Insights:

1. Two-Pointer Technique:
   • Utilize two pointers starting at the beginning (left) and end (right) of the subarray
   • Swap the elements at these pointers and move them towards each other until they meet or cross
2. Recursive Reversal:
   • Implement the two-pointer swapping recursively
   • Base Case: If left is greater than or equal to right, terminate the recursion
   • Recursive Case: Swap the elements at left and right, then recursively call the function with left + 1 and right – 1
3. Index Adjustment: Convert the 1-based indices “l” and “r” to 0-based indices for array manipulation

Approach Overview:

1. Index Conversion: Adjust the provided 1-based indices “l” and “r” to 0-based indices suitable for Python lists
2. Recursive Function (func):
   • Swap elements at the left and right positions
   • Recursively call itself with updated indices to continue swapping inward elements
3. Wrapper Function (reverseSubArray):
   • Serve as an interface that initiates the recursive reversal
   • Return the modified array after the reversal process

Why This Works:

• Efficiency: The recursive approach ensures that each pair of elements is swapped exactly once, leading to a time complexity of O(n), where “n” is the number of elements in the subarray.
• In-Place Modification: By swapping elements within the original array, the approach maintains constant space complexity (O(1)), as no additional data structures are required.

Code:

class Solution:
    def func(self, arr, left, right):
        if left >= right:
            return
        arr[left], arr[right] = arr[right], arr[left]
        self.func(arr, left + 1, right - 1)
   
    def reverseSubArray(self, arr, l, r):
        self.func(arr, l-1, r-1)
        return arr

The solution consists of two primary functions:

1. func Function:
   • Purpose: Recursively swaps elements in the array to reverse the specified subarray
   • Mechanism:
     • Base Case: If the left index is greater than or equal to the right index, the recursion terminates as all necessary swaps have been completed.
     • Recursive Case:
       • Swap the elements at the left and right indices.
       • Recursively call “func” with incremented left and decremented right to continue swapping the next pair inward.
2. reverseSubArray Function:
   • Purpose: Acts as a wrapper that prepares the indices and initiates the recursive reversal
   • Mechanism:
     • Convert the 1-based indices “l” and “r” to 0-based indices by subtracting 1
     • Call the “func” function with the adjusted indices to perform the reversal
     • Return the modified array after the reversal is complete

Highlights:

• Recursion Depth: The depth of recursion corresponds to half the length of the subarray, ensuring that each pair is swapped once.
• In-Place Swapping: By swapping elements directly within the array, the algorithm avoids the need for additional memory, maintaining space efficiency.
• Index Handling: Adjusting indices from 1-based to 0-based ensures correct element access within the Python list.

Dry Run:

Let’s walk through an example to understand how the code operates step by step.

Example:

• Input:
  • arr = [1, 2, 3, 4, 5]
  • l = 2
  • r = 4
• Expected Output: [1, 4, 3, 2, 5]

Process:

1. Initial Setup:
   • Convert l and r to 0-based indices:
     • l-1 = 1
     • r-1 = 3
   • Array before reversal: [1, 2, 3, 4, 5]
2. First Call to func(arr, 1, 3):
   • Check Base Case:
     1 < 3 → Proceed.
   • Swap Elements at Indices 1 and 3:
     • Swap arr[1] (2) with arr[3] (4).
     • Array after swap: [1, 4, 3, 2, 5]
   • Recursive Call:
     func(arr, 2, 2)
3. Second Call to func(arr, 2, 2):
   • Check Base Case:
     2 >= 2 → Terminate recursion.
4. Final Array After Reversal:
   [1, 4, 3, 2, 5]

Result: The subarray from index 2 to 4 has been successfully reversed.

Another Example:

• Input:
  • arr = [10, 20, 30, 40, 50, 60]
  • l = 1
  • r = 6
• Expected Output: [60, 50, 40, 30, 20, 10]

Process:

1. Initial Setup:
   • Convert l and r to 0-based indices:
     • l-1 = 0
     • r-1 = 5
   • Array before reversal: [10, 20, 30, 40, 50, 60]
2. First Call to func(arr, 0, 5):
   • Check Base Case: 0 < 5 → Proceed.
   • Swap Elements at Indices 0 and 5:
     • Swap arr[0] (10) with arr[5] (60).
     • Array after swap: [60, 20, 30, 40, 50, 10]
   • Recursive Call: func(arr, 1, 4)
3. Second Call to func(arr, 1, 4):
   • Check Base Case: 1 < 4 → Proceed.
   • Swap Elements at Indices 1 and 4:
     • Swap arr[1] (20) with arr[4] (50).
     • Array after swap: [60, 50, 30, 40, 20, 10]
   • Recursive Call: func(arr, 2, 3)
4. Third Call to func(arr, 2, 3):
   • Check Base Case: 2 < 3 → Proceed.
   • Swap Elements at Indices 2 and 3:
     • Swap arr[2] (30) with arr[3] (40).
     • Array after swap: [60, 50, 40, 30, 20, 10]
   • Recursive Call: func(arr, 3, 2)
5. Fourth Call to func(arr, 3, 2):
   • Check Base Case: 3 >= 2 → Terminate recursion.
6. Final Array After Reversal: [60, 50, 40, 30, 20, 10]

Result: The entire array has been successfully reversed.

Edge Cases:

Handling edge cases ensures that the function behaves correctly under all possible scenarios.

1. Subarray of Length 1:
   • Input:
     • arr = [5, 6, 7, 8, 9]
     • l = 3
     • r = 3
   • Expected Output: [5, 6, 7, 8, 9]
   • Explanation: Reversing a subarray of length 1 doesn’t change the array.
2. Entire Array Reversal:
   • Input:
     • arr = [1, 2, 3, 4]
     • l = 1
     • r = 4
   • Expected Output: [4, 3, 2, 1]
   • Explanation: Reversing the entire array.
3. Subarray at the Beginning:
   • Input:
     • arr = [10, 20, 30, 40, 50]
     • l = 1
     • r = 3
   • Expected Output: [30, 20, 10, 40, 50]
   • Explanation: Reversing the first three elements.
4. Subarray at the End:
   • Input:
     • arr = [100, 200, 300, 400]
     • l = 3
     • r = 4
   • Expected Output: [100, 200, 400, 300]
   • Explanation: Reversing the last two elements.
5. Array with All Identical Elements:
   • Input:
     • arr = [7, 7, 7, 7, 7]
     • l = 2
     • r = 4
   • Expected Output: [7, 7, 7, 7, 7]
   • Explanation: Reversing doesn’t change the array as all elements are identical.
6. Invalid Indices (Assuming Input Validation):
   • Input:
     • arr = [1, 2, 3]
     • l = 4
     • r = 5
   • Expected Behavior:
     • The function assumes valid input as per constraints.
     • If implemented with input validation, it should handle or reject such cases gracefully.

Time and Space Complexity:

Time Complexity: O(n)

• Explanation:
  • Reversal Function (func):
    • The function recursively swaps elements from the ends towards the center.
    • It makes approximately (r−l+1)/2 recursive calls, where n = r − l + 1 is the length of the subarray.
    • Each call performs a constant amount of work (swapping two elements).
    • Overall: Linear time relative to the size of the subarray.
• Wrapper Function (reverseSubArray): Initiates the reversal process with O(1) additional operations.
• Combined: The total time complexity is O(n), where n is the number of elements in the subarray being reversed.

Space Complexity: O(n) due to Recursion

• Explanation:
  • Recursive Calls:
    • Each recursive call adds a new frame to the call stack.
    • For a subarray of size n, there are n/2​ recursive calls.
    • Space Used: O(n) due to recursion depth.
• Auxiliary Space: No additional data structures are used; only a few variables for swapping.
• Overall: The space complexity is linear, O(n), primarily due to the recursive stack.

Note: For large subarrays, deep recursion may lead to stack overflow errors in environments with limited recursion depth. An iterative approach can achieve O(1) space complexity by eliminating recursion.

Also read about the Python Program to Find Factorial of Number Using Recursion.

2.WHILE LOOP SOLUTION

Problem Statement:

Given:

• An array of integers “arr”
• Two integers “l” and “r”, representing the starting and ending positions (1-based indices) of a subarray within “arr”

Task:

• Reverse the elements of the subarray from position “l” to position “r” in-place
• Return the modified array after performing the reversal

Constraints:

• 1 <= l <= r <= len(arr)
• 1 <= len(arr) <= 10^5
• -10^9 <= arr[i] <= 10^9

Examples:

Example 1:

  Input: arr = [1, 2, 3, 4, 5], l = 2, r = 4
  Output: [1, 4, 3, 2, 5]
  Explanation: The subarray from index 2 to 4 is [2, 3, 4]. Reversing it results in [4, 3, 2], so the entire array becomes [1, 4, 3, 2, 5].

Example 2:

  Input: arr = [10, 20, 30, 40, 50, 60], l = 1, r = 6
  Output: [60, 50, 40, 30, 20, 10]
  Explanation: Reversing the entire array.

Example 3:

  Input: arr = [5, 4, 3, 2, 1], l = 3, r = 3
  Output: [5, 4, 3, 2, 1]
  Explanation: Reversing a single element doesn't change the array.

Intuition and Approach:

Objective: Efficiently reverse a specified portion of an array in-place without using additional memory for another array.

Key Insights:

1. Two-Pointer Technique:
   • Utilize two pointers, left and right, starting at the beginning (l-1) and end (r-1) of the subarray respectively
   • Swap the elements at these pointers
   • Move left forward and right backward, repeating the process until left is no longer less than right
2. In-Place Reversal: By swapping elements within the original array, we avoid the need for extra space, ensuring space efficiency.
3. 1-Based to 0-Based Indexing: Since array indices in most programming languages (including Python) are 0-based, adjust the given 1-based indices “l” and “r” by subtracting 1 to align with the array’s indexing.

Step-by-Step Approach:

1. Index Adjustment: Convert the 1-based indices l and r to 0-based indices by computing left = l – 1 and right = r – 1.
2. Initialize Pointers: Set left to l – 1 and right to r – 1.
3. Iterative Swapping:
   • While left < right:
     • Swap arr[left] with arr[right].
     • Increment left by 1.
     • Decrement right by 1.
4. Termination: The loop terminates when left is no longer less than right, indicating that the subarray has been fully reversed.
5. Return the Modified Array: After the reversal, return the updated array “arr”

Why This Works:

• Efficiency: The two-pointer technique ensures that each element in the subarray is visited only once, resulting in a time complexity of O(n), where n=r−l+1 is the length of the subarray.
• Space Optimization: By performing swaps in-place, the algorithm maintains a constant space complexity of O(1), as no additional data structures are required.
• Simplicity: The approach is straightforward and easy to implement, reducing the likelihood of errors.

Code:

class Solution:     def reverseSubArray(self, arr, l, r):         while left<right:             arr[left],arr[right]=arr[right],arr[left]             left+=1             right-=1         return arr

Components of the Code:

1. Function Definition:
   • Function Name: reverseSubArray
   • Parameters:
     • arr: The original array of integers.
     • l: The starting position (1-based index) of the subarray to be reversed.
     • r: The ending position (1-based index) of the subarray to be reversed.
   • Return Value: The modified array after reversing the specified subarray.
2. Loop Structure:
   • The function uses a while loop that continues as long as left < right.
   • Purpose: To iterate over the subarray from both ends towards the center, swapping elements to achieve the reversal.
3. Swapping Elements:
   • arr[left], arr[right] = arr[right], arr[left]
   • Action: Swaps the elements at positions left and right.
   • Result: Moves the element from the end to the beginning and vice versa within the subarray.
4. Pointer Adjustment:
   • left += 1: Moves the left pointer one step to the right.
   • right -= 1: Moves the right pointer one step to the left.
   • Purpose: Continues the traversal towards the center of the subarray after each swap.
5. Return Statement:
   • return arr
   • Action: Returns the modified array after completing the reversal process.

Assumptions and Clarifications:

• Index Initialization: The variables left and right should be initialized before entering the while loop. Based on the problem statement and typical implementation, it’s implied that left = l – 1 and right = r – 1 to convert 1-based indices to 0-based.
• Correctness of Indices: The function assumes that the provided indices l and r are valid (i.e., 1 <= l <= r <= len(arr)). Handling of invalid indices is not included and should be managed externally or by incorporating additional checks.

Dry Run:

To illustrate how the “reverseSubArray” function operates, let’s walk through an example step by step.

Edge Cases:

Ensuring that the reverseSubArray function handles all possible scenarios correctly is vital for its robustness. Here are some noteworthy edge cases:

1. Subarray of Length 1:
   • Input:
     • arr = [5, 6, 7, 8, 9]
     • l = 3
     • r = 3
   • Expected Output: [5, 6, 7, 8, 9]
   • Explanation: Reversing a subarray that contains only one element (7) doesn’t change the array.
2. Entire Array Reversal:
   • Input:
     • arr = [1, 2, 3, 4]
     • l = 1
     • r = 4
   • Expected Output: [4, 3, 2, 1]
   • Explanation: Reversing the entire array results in a completely inverted sequence.
3. Subarray at the Beginning:
   • Input:
     • arr = [10, 20, 30, 40, 50]
     • l = 1
     • r = 3
   • Expected Output: [30, 20, 10, 40, 50]
   • Explanation: Reversing the first three elements transforms [10, 20, 30] to [30, 20, 10].
4. Subarray at the End:
   • Input:
     • arr = [100, 200, 300, 400]
     • l = 3
     • r = 4
   • Expected Output: [100, 200, 400, 300]
   • Explanation: Reversing the last two elements swaps 300 and 400.
5. Array with All Identical Elements:
   • Input:
     • arr = [7, 7, 7, 7, 7]
     • l = 2
     • r = 4
   • Expected Output: [7, 7, 7, 7, 7]
   • Explanation: Reversing a subarray where all elements are identical results in no visible change.
6. Invalid Indices (Assuming Input Validation):
   • Input:
     • arr = [1, 2, 3]
     • l = 4
     • r = 5
   • Expected Behavior:
     • The function assumes valid input as per constraints.
     • If implemented with input validation, it should handle or reject such cases gracefully, possibly by raising an error or ignoring the operation.
   • Explanation: Since l = 4 and r = 5 exceed the array bounds (len(arr) = 3), the function should ideally validate inputs before proceeding.
7. Empty Subarray (When l > r):
   • Input:
     • arr = [1, 2, 3, 4, 5]
     • l = 5
     • r = 3
   • Expected Behavior:
     • According to constraints, l <= r, so such input should be considered invalid.
     • The function may either perform no operation or handle it based on implementation specifics.
   • Explanation: Reversing from a higher index to a lower one doesn’t make sense and should be handled appropriately.

Time and Space Complexity:

Time Complexity: O(n)

• Explanation:
  • Loop Iterations:
    • The while loop runs as long as left < right
    • For a subarray of length n = r – l + 1, the number of iterations is approximately n/2
    • Each iteration performs a constant-time swap operation
  • Overall: The time complexity scales linearly with the size of the subarray, O(n)

Space Complexity: O(1)

• Explanation:
  • In-Place Operations: The function performs swaps directly within the original array, requiring no additional space proportional to input size
  • Variables Used: Only a fixed number of variables (left, right) are used, regardless of the input size
  • Overall: The space complexity remains constant, O(1)

---

For any changes to the document, kindly email at code@codeanddebug.in or contact us at +91-9712928220.