# How to Left Rotate an Array by D Positions

Left rotating an array involves shifting the elements of the array to the left by a specified number of places. In this article, we'll discuss two efficient methods to achieve this rotation.

### Solution 1: Brute Force Approach (using a Temp Array)

This method uses an auxiliary array to store the first D elements and then shifts the rest of the elements to the left.

**Implementation**:

```cpp
// Solution-1: Using a Temp Array
// Time Complexity: O(n)
// Space Complexity: O(k)
// since k array elements need to be stored in temp array
void leftRotate(int arr[], int n, int k)
{
    // Adjust k to be within the valid range (0 to n-1)
    k = k % n;

    // Handle edge case: empty array
    if (n == 0)
    {
        return;
    }

    int temp[k];

    // Storing k elements in temp array from the left
    for (int i = 0; i < k; i++)
    {
        temp[i] = arr[i];
    }

    // Shifting the rest of elements to the left
    for (int i = k; i < n; i++)
    {
        arr[i - k] = arr[i];
    }

    // Putting k elements back to main array
    for (int i = n - k; i < n; i++)
    {
        arr[i] = temp[i - n + k];
    }
}
```

**Logic**:

1. **Adjust k**: Ensure `k` is within the valid range by taking `k % n`.
    
2. **Store in Temp**: Store the first `k` elements in a temporary array.
    
3. **Shift Elements**: Shift the remaining elements of the array to the left by `k` positions.
    
4. **Copy Back**: Copy the elements from the temporary array back to the end of the main array.
    

**Time Complexity**: O(n)

* **Explanation**: Each element is moved once.
    

**Space Complexity**: O(k)

* **Explanation**: An additional array of size `k` is used.
    

**Example**:

* **Input**: `arr = [1, 2, 3, 4, 5, 6, 7]`, `k = 3`
    
* **Output**: `arr = [4, 5, 6, 7, 1, 2, 3]`
    
* **Explanation**: The first 3 elements `[1, 2, 3]` are stored in a temp array, the rest are shifted left and then the temp array is copied back to the end.
    

---

### Solution 2: Optimal Approach (using Reversal Algorithm)

This method uses a three-step reversal process to achieve the rotation without needing **extra space**.

**Implementation**:

```cpp
// Solution-2: Using Reversal Algorithm
// Time Complexity: O(n)
// Space Complexity: O(1)

// Function to Reverse Array
void reverseArray(int arr[], int start, int end)
{
    while (start < end)
    {
        int temp = arr[start];
        arr[start] = arr[end];
        arr[end] = temp;
        start++;
        end--;
    }
}

// Function to Rotate k elements to the left
void leftRotate(int arr[], int n, int k)
{
    // Adjust k to be within the valid range (0 to n-1)
    k = k % n;

    // Handle edge case: empty array
    if (n == 0)
    {
        return;
    }

    // Reverse first k elements
    reverseArray(arr, 0, k - 1);

    // Reverse last n-k elements
    reverseArray(arr, k, n - 1);

    // Reverse whole array
    reverseArray(arr, 0, n - 1);
}
```

**Logic**:

1. **Adjust k**: Ensure `k` is within the valid range by taking `k % n`.
    
2. **Reverse First Part**: Reverse the first `k` elements.
    
3. **Reverse Second Part**: Reverse the remaining `n-k` elements.
    
4. **Reverse Entire Array**: Reverse the entire array to achieve the final rotated array.
    

**Time Complexity**: O(n)

* **Explanation**: The array is reversed three times, each taking O(n) time.
    

**Space Complexity**: O(1)

* **Explanation**: The algorithm operates in place, using only a constant amount of extra space.
    

**Example**:

* **Input**: `arr = [1, 2, 3, 4, 5, 6, 7]`, `k = 3`
    
* **Output**: `arr = [4, 5, 6, 7, 1, 2, 3]`
    
* **Explanation**:
    
    * Reverse the first 3 elements: `[3, 2, 1, 4, 5, 6, 7]`
        
    * Reverse the last 4 elements: `[3, 2, 1, 7, 6, 5, 4]`
        
    * Reverse the entire array: `[4, 5, 6, 7, 1, 2, 3]`
        

---

### Comparison

* **Brute Force Method (Using Temp Array)**:
    
    * **Pros**: Simple and easy to understand.
        
    * **Cons**: Uses additional space for the temporary array, which may not be efficient for large values of `k`.
        
* **Optimal Method (Using Reversal Algorithm)**:
    
    * **Pros**: Efficient with O(n) time complexity and O(1) space complexity.
        
    * **Cons**: Slightly more complex to implement but highly efficient for large arrays.
        

### Edge Cases

* **Empty Array**: Returns immediately as there are no elements to rotate.
    
* **k &gt;= n**: Correctly handles cases where `k` is greater than or equal to the array length by using `k % n`.
    
* **Single Element Array**: Returns the same array as it only contains one element.
    

### Additional Notes

* **Efficiency**: The reversal algorithm is more space-efficient, making it preferable for large arrays.
    
* **Practicality**: Both methods handle rotations efficiently but the choice depends on space constraints.
    

### Conclusion

Left rotating an array by `k` positions can be efficiently achieved using either a temporary array or an in-place reversal algorithm. The optimal choice depends on the specific constraints and requirements of the problem.

---