Given an array nums of size n, return the majority element.

The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.

### Majority Element Explanation and Solution Approach

The majority element in an array is the element that appears more than half the time in the array. For example, in an array of size \( n \), the majority element is the one that appears more than \( \frac{n}{2} \) times.

### Approach
The provided solution sorts the array and then returns the middle element. Here's why this works:

1. Sorting: When the array is sorted, the majority element will occupy the middle position because it appears more than half the times. Thus, in a sorted array, the element at the index \( n/2 \) (where \( n \) is the size of the array) is guaranteed to be the majority element.

2. Return Middle Element: Since the majority element must appear at least \( \frac{n}{2} + 1 \) times, it will necessarily be present at the \( n/2 \)-th position in the sorted array.

### Time and Space Complexity
- Time Complexity: Sorting the array takes \( O(n \log n) \), where \( n \) is the size of the array.
- Space Complexity: The space complexity is \( O(1) \) if the sorting algorithm used is in-place (like quicksort or heapsort). Otherwise, it is \( O(n) \) for algorithms like mergesort which require additional space.

### Detailed Example

#### Example 1
Input: nums = [3, 2, 3]
- Step 1: Sort the array: [2, 3, 3]
- Step 2: Find the middle element: The element at index \( 1 \) (which is \( \lfloor \frac{3}{2} \rfloor \)) is 3.

Output: 3

#### Example 2
Input: nums = [2, 2, 1, 1, 1, 2, 2]
- Step 1: Sort the array: [1, 1, 1, 2, 2, 2, 2]
- Step 2: Find the middle element: The element at index \( 3 \) (which is \( \lfloor \frac{7}{2} \rfloor \)) is 2.

Output: 2

### Code Implementation

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        return nums[n / 2];
    }
};

### Explanation with All Iterations for the Given Inputs

#### Example 1: nums = [3, 2, 3]

1. Initial Array: [3, 2, 3]
2. After Sorting: [2, 3, 3]
3. Middle Element: nums[3 / 2] = nums[1] = 3
4. Result: 3

#### Example 2: nums = [2, 2, 1, 1, 1, 2, 2]

1. Initial Array: [2, 2, 1, 1, 1, 2, 2]
2. After Sorting: [1, 1, 1, 2, 2, 2, 2]
3. Middle Element: nums[7 / 2] = nums[3] = 2
4. Result: 2

This approach is simple and leverages the properties of sorted arrays to find the majority element effectively. However, it is not the most optimal in terms of time complexity. More efficient solutions exist, such as using the Boyer-Moore Voting Algorithm, which can find the majority element in \( O(n) \) time and \( O(1) \) space.

Trapping Rain Water

The provided code solves the "Trapping Rain Water" problem using dynamic programming. It calculates the amount of water that can be trapped after raining for each bar in the given height map. Let's break down the code and explain how it works using the given input.

### Code Explanation

class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();

        vector<int> left(n, 0);
        vector<int> right(n, 0);

        left[0] = height[0];
        right[n - 1] = height[n - 1];

        for (int i = 1; i < n; i++) {
            left[i] = max(left[i - 1], height[i]);
        }

        for (int i = n - 2; i >= 0; i--) {
            right[i] = max(right[i + 1], height[i]);
        }

        int ans = 0;
        for (int i = 0; i < n; i++) {
            ans += min(left[i], right[i]) - height[i];
        }

        return ans;
    }
};

### Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]

### Output: 6

### Explanation:

1. Initialization:
- height array: [0,1,0,2,1,0,1,3,2,1,2,1]
- n (size of the array): 12
- left and right arrays: Both initialized with size 12 filled with 0.

2. Filling `left` array:
- left[i] will store the maximum height from the left up to index i.

   left[0] = height[0] = 0
   for (int i = 1; i < n; i++) {
       left[i] = std::max(left[i - 1], height[i]);
   }
   

Resulting left array:
[0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3]

3. Filling `right` array:
- right[i] will store the maximum height from the right up to index i.

   right[n - 1] = height[n - 1] = 1
   for (int i = n - 2; i >= 0; i--) {
       right[i] = std::max(right[i + 1], height[i]);
   }
   

Resulting right array:
[3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 1]

4. Calculating trapped water:
- For each index i, the trapped water is calculated as the difference between the minimum of left[i] and right[i] and the height at index i.

   int ans = 0;
   for (int i = 0; i < n; i++) {
       ans += std::min(left[i], right[i]) - height[i];
   }
   

Water trapped at each index:
- Index 0: 0
- Index 1: 0
- Index 2: 1
- Index 3: 0
- Index 4: 1
- Index 5: 2
- Index 6: 1
- Index 7: 0
- Index 8: 0
- Index 9: 1
- Index 10: 0
- Index 11: 0

Sum of trapped water: 0 + 0 + 1 + 0 + 1 + 2 + 1 + 0 + 0 + 1 + 0 + 0 = 6

### Conclusion:
The solution efficiently computes the amount of water trapped by utilizing two auxiliary arrays (left and right) to store the maximum heights to the left and right of each position. This approach ensures that each element is processed in linear time, resulting in an overall time complexity of O(n). The given input results in a total of 6 units of water being trapped.

sort colors

### Dutch National Flag Problem Approach for Sorting Colors

The goal is to sort an array consisting of 0s, 1s, and 2s in a single pass using constant space. This is known as the Dutch National Flag problem.

### Approach
We maintain three pointers:
- left: Tracks the boundary of 0s.
- right: Tracks the boundary of 2s.
- i: Iterates through the array.

Here's how it works:
1. If arr[i] is 0, we swap it with arr[left] and increment both i and left.
2. If arr[i] is 2, we swap it with arr[right] and decrement right.
3. If arr[i] is 1, we just increment i.

This ensures that by the end of the loop, all 0s are at the beginning, all 2s are at the end, and all 1s are in the middle.

### Time and Space Complexity
- Time Complexity: O(n), where n is the size of the array. Each element is processed at most once.
- Space Complexity: O(1), because we are not using any extra space apart from a few variables.

### Code Implementation

class Solution {
public:
    void sortColors(vector<int>& arr) {
        int left = 0, right = arr.size() - 1;
        int i = 0;
        
        while (i <= right) {
            if (arr[i] == 0) {
                swap(arr[i], arr[left]);
                i++;
                left++;
            } else if (arr[i] == 2) {
                swap(arr[i], arr[right]);
                right--;
            } else {
                i++;
            }
        }
    }
};

### Detailed Example with Iterations

#### Input: nums = [2, 0, 2, 1, 1, 0]
- Initial Array: [2, 0, 2, 1, 1, 0]
- Initial State: left = 0, right = 5, i = 0

Iteration 1:
- i = 0, arr[i] = 2
- Swap arr[i] with arr[right]
- After swapping: nums = [0, 0, 2, 1, 1, 2]
- Decrement right to 4
- i remains 0

Iteration 2:
- i = 0, arr[i] = 0
- Swap arr[i] with arr[left]
- After swapping: nums = [0, 0, 2, 1, 1, 2] (no actual change)
- Increment both left to 1 and i to 1

Iteration 3:
- i = 1, arr[i] = 0
- Swap arr[i] with arr[left]
- After swapping: nums = [0, 0, 2, 1, 1, 2] (no actual change)
- Increment both left to 2 and i to 2

Iteration 4:
- i = 2, arr[i] = 2
- Swap arr[i] with arr[right]
- After swapping: nums = [0, 0, 1, 1, 2, 2]
- Decrement right to 3
- i remains 2

Iteration 5:
- i = 2, arr[i] = 1
- Do nothing, just increment i to 3

Iteration 6:
- i = 3, arr[i] = 1
- Do nothing, just increment i to 4

End of Loop: i is now greater than right

Final Array: [0, 0, 1, 1, 2, 2]

### Summary of Each Iteration:
1. Iteration 1: Swap 2 with 0, nums becomes [0, 0, 2, 1, 1, 2], right becomes 4, i stays 0.
2. Iteration 2: Swap 0 with 0, nums stays [0, 0, 2, 1, 1, 2], increment left to 1, i to 1.
3. Iteration 3: Swap 0 with 0, nums stays [0, 0, 2, 1, 1, 2], increment left to 2, i to 2.
4. Iteration 4: Swap 2 with 2, nums becomes [0, 0, 1, 1, 2, 2], right becomes 3, i stays 2.
5. Iteration 5: Encounter 1, increment i to 3.
6. Iteration 6: Encounter 1, increment i to 4.

This approach sorts the array efficiently in a single pass with O(n) time complexity.

Conatiner With most water

### Problem: Container With Most Water

You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the i`th line are (i, 0) and (i, height[i])`.

Find two lines that together with the x-axis form a container, such that the container contains the most water.

Return the maximum amount of water a container can store.

### Approach

To solve this problem efficiently, we use the two-pointer technique. The idea is to start with the widest possible container and then systematically narrow the width while keeping track of the maximum area.

1. Initialization:
- Set two pointers: left at the start (index 0) and right at the end (index n - 1) of the array.
- Initialize a variable ans to store the maximum area found.

2. Iterate with Two Pointers:
- Calculate the height of the container using the shorter of the two lines pointed to by left and right.
- Calculate the width of the container as right - left.
- Calculate the area as heightOfContainer * widthOfContainer.
- Update ans if the calculated area is greater than the current ans.
- Move the pointer pointing to the shorter line inward to try and find a taller line:
- If height[left] is less than height[right], move the left pointer to the right (left++).
- Otherwise, move the right pointer to the left (right--).

3. Termination:
- The loop terminates when the left pointer meets or surpasses the right pointer.

### Time and Space Complexity

- Time Complexity: O(n), where n is the length of the height array. This is because each element is processed at most once.
- Space Complexity: O(1), as no additional space proportional to the input size is used.

### Code Implementation

class Solution {
public:
    int maxArea(vector<int>& height) {
        int left = 0;
        int right = height.size() - 1;
        int ans = 0;
        
        while (left < right) {
            int heightOfContainer = min(height[left], height[right]);
            int widthOfContainer = right - left;
            int area = heightOfContainer * widthOfContainer;
            if (area > ans) {
                ans = area;
            }
            
            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }
        
        return ans;
    }
};

### Example Iterations

#### Input: height = [1, 8, 6, 2, 5, 4, 8, 3, 7]

1. Initial State:
- left = 0, right = 8, ans = 0

2. Iteration 1:
- height[left] = 1, height[right] = 7
- heightOfContainer = min(1, 7) = 1
- widthOfContainer = 8 - 0 = 8
- area = 1 * 8 = 8
- ans = max(0, 8) = 8
- Move left to 1 (since height[left] < height[right])

3. Iteration 2:
- left = 1, right = 8
- height[left] = 8, height[right] = 7
- heightOfContainer = min(8, 7) = 7
- widthOfContainer = 8 - 1 = 7
- area = 7 * 7 = 49
- ans = max(8, 49) = 49
- Move right to 7 (since height[left] >= height[right])

4. Iteration 3:
- left = 1, right = 7
- height[left] = 8, height[right] = 3
- heightOfContainer = min(8, 3) = 3
- widthOfContainer = 7 - 1 = 6
- area = 3 * 6 = 18
- ans = max(49, 18) = 49
- Move right to 6 (since height[left] >= height[right])

5. Iteration 4:
- left = 1, right = 6
- height[left] = 8, height[right] = 8
- heightOfContainer = min(8, 8) = 8
- widthOfContainer = 6 - 1 = 5
- area = 8 * 5 = 40
- ans = max(49, 40) = 49
- Move right to 5 (since height[left] >= height[right])

6. Iteration 5:
- left = 1, right = 5
- height[left] = 8, height[right] = 4
- heightOfContainer = min(8, 4) = 4
- widthOfContainer = 5 - 1 = 4
- area = 4 * 4 = 16
- ans = max(49, 16) = 49
- Move right to 4 (since height[left] >= height[right])

7. Iteration 6:
- left = 1, right = 4
- height[left] = 8, height[right] = 5
- heightOfContainer = min(8, 5) = 5
- widthOfContainer = 4 - 1 = 3
- area = 5 * 3 = 15
- ans = max(49, 15) = 49
- Move right to 3 (since height[left] >= height[right])

8. Iteration 7:
- left = 1, right = 3
- height[left] = 8, height[right] = 2
- heightOfContainer = min(8, 2) = 2
- widthOfContainer = 3 - 1 = 2
- area = 2 * 2 = 4
- ans = max(49, 4) = 49
- Move right to 2 (since height[left] >= height[right])

9. Iteration 8:
- left = 1, right = 2
- height[left] = 8, height[right] = 6
- heightOfContainer = min(8, 6) = 6
- widthOfContainer = 2 - 1 = 1
- area = 6 * 1 = 6
- ans = max(49, 6) = 49
- Move right to 1 (since height[left] >= height[right])

10. End of Loop:
- left = 1, right = 1
- The loop ends as left is not less than right.

### Final Output
- Maximum Area: 49

The maximum area of water the container can store is 49, achieved with the lines at positions 1 and 8.

Single Number

### Problem Statement

Given a non-empty array of integers nums, every element appears twice except for one. Find that single one. The solution must have linear runtime complexity and use only constant extra space.

### Approach

To solve this problem efficiently, we can use the XOR bitwise operator. The properties of XOR are:

1. \(a \oplus a = 0\) for any integer \(a\).
2. \(a \oplus 0 = a\) for any integer \(a\).
3. XOR is commutative and associative, meaning the order of operations does not change the result.

Using these properties, if we XOR all the elements in the array, the elements that appear twice will cancel out each other (i.e., result in 0), and we will be left with the single element that appears only once.

### Steps

1. Initialize a variable ans to 0.
2. Iterate through each element in the array and XOR it with ans.
3. The result stored in ans at the end of the iteration will be the single element.

### Complexity Analysis

- Time Complexity: \(O(n)\), where \(n\) is the number of elements in the array. We only make one pass through the array.
- Space Complexity: \(O(1)\). We use a constant amount of extra space (the variable ans).

### Code

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ans = 0;
        for(int num : nums){
            ans = ans ^ num;
        }
        return ans;
    }
};

### Explanation with Iterations

For the input nums = [4, 1, 2, 1, 2]:

1. Initial State:
- ans = 0

2. Iteration 1 (num = 4):
- ans = ans ^ 4
- ans = 0 ^ 4 = 4

3. Iteration 2 (num = 1):
- ans = ans ^ 1
- ans = 4 ^ 1 = 5

4. Iteration 3 (num = 2):
- ans = ans ^ 2
- ans = 5 ^ 2 = 7

5. Iteration 4 (num = 1):
- ans = ans ^ 1
- ans = 7 ^ 1 = 6

6. Iteration 5 (num = 2):
- ans = ans ^ 2
- ans = 6 ^ 2 = 4

### Final Output

- ans = 4

The single element that appears only once in the array nums is 4.

Pascals Triangle

### Approach Explanation

The task is to generate Pascal's Triangle up to a given number of rows (numRows). Pascal's Triangle is a triangular array where the value at each position is the sum of the two values directly above it from the previous row. Here's a step-by-step explanation of the approach:

1. Initialization:
- Create an empty 2D vector ans to store the rows of Pascal's Triangle.

2. Outer Loop (Rows):
- Iterate from 0 to numRows - 1 using the variable r.
- For each iteration, create a new vector row of size r + 1, initialized with 1`s. This automatically sets the first and last elements of each row to `1.

3. Inner Loop (Columns):
- Iterate from 1 to r - 1 using the variable c (excluding the first and last positions which are already 1).
- Calculate the value at each position c in the current row as the sum of the values from the previous row at positions c - 1 and c.

4. Add the Row to Result:
- After filling in all the required values for the current row, add the row to the ans vector.

5. Return the Result:
- After all rows are generated, return the ans vector containing Pascal's Triangle.

### Detailed Iteration Example

Let's walk through an example where numRows = 5:

1. Initialization:
- ans is initialized as an empty vector.

2. Iteration 0:
- r = 0: Create row = [1].
- ans = [[1]].

3. Iteration 1:
- r = 1: Create row = [1, 1].
- ans = [[1], [1, 1]].

4. Iteration 2:
- r = 2: Create row = [1, 1, 1].
- Inner loop: c = 1, calculate row[1] = ans[1][0] + ans[1][1] = 1 + 1 = 2.
- row = [1, 2, 1].
- ans = [[1], [1, 1], [1, 2, 1]].

5. Iteration 3:
- r = 3: Create row = [1, 1, 1, 1].
- Inner loop: c = 1, calculate row[1] = ans[2][0] + ans[2][1] = 1 + 2 = 3.
- Inner loop: c = 2, calculate row[2] = ans[2][1] + ans[2][2] = 2 + 1 = 3.
- row = [1, 3, 3, 1].
- ans = [[1], [1, 1], [1, 2, 1], [1, 3, 3, 1]].

6. Iteration 4:
- r = 4: Create row = [1, 1, 1, 1, 1].
- Inner loop: c = 1, calculate row[1] = ans[3][0] + ans[3][1] = 1 + 3 = 4.
- Inner loop: c = 2, calculate row[2] = ans[3][1] + ans[3][2] = 3 + 3 = 6.
- Inner loop: c = 3, calculate row[3] = ans[3][2] + ans[3][3] = 3 + 1 = 4.
- row = [1, 4, 6, 4, 1].
- ans = [[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]].

### Time and Space Complexity

Time Complexity:
- The outer loop runs numRows times.
- The inner loop runs r times for each r from 1 to numRows - 1.
- The total number of operations is the sum of the first numRows integers, which is \(\sum_{r=1}^{numRows} r = \frac{numRows \times (numRows + 1)}{2}\).
- Thus, the time complexity is \(O(numRows^2)\).

Space Complexity:
- We store the results in a 2D vector ans.
- The total number of elements in ans is \(\sum_{r=1}^{numRows} r = \frac{numRows \times (numRows + 1)}{2}\).
- Thus, the space complexity is also \(O(numRows^2)\).

Sure, let's go through the detailed explanation along with the provided code to understand each iteration and the time and space complexity.

### Code

Here is the corrected and efficient implementation of the Pascal's Triangle generator:

#include <vector>
using namespace std;

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> ans; // Resultant 2D vector

        for (int r = 0; r < numRows; ++r) {
            vector<int> row(r + 1, 1); // Create a row with r+1 elements, all initialized to 1

            for (int c = 1; c < r; ++c) {
                // Calculate the value based on the values from the previous row
                row[c] = ans[r - 1][c - 1] + ans[r - 1][c];
            }

            ans.push_back(row); // Add the row to the result
        }

        return ans;
    }
};

### Detailed Iteration Example

Let's go through an example where numRows = 5:

1. Initialization:
- vector<vector<int>> ans; initializes an empty vector to store the rows of Pascal's Triangle.

2. Iteration 0:
- r = 0: Create row = [1].
- Add row to ans.
- ans = [[1]].

3. Iteration 1:
- r = 1: Create row = [1, 1].
- Add row to ans.
- ans = [[1], [1, 1]].

4. Iteration 2:
- r = 2: Create row = [1, 1, 1].
- Inner loop: c = 1, calculate row[1] = ans[1][0] + ans[1][1] = 1 + 1 = 2.
- row = [1, 2, 1].
- Add row to ans.
- ans = [[1], [1, 1], [1, 2, 1]].

5. Iteration 3:
- r = 3: Create row = [1, 1, 1, 1].
- Inner loop: c = 1, calculate row[1] = ans[2][0] + ans[2][1] = 1 + 2 = 3.
- Inner loop: c = 2, calculate row[2] = ans[2][1] + ans[2][2] = 2 + 1 = 3.
- row = [1, 3, 3, 1].
- Add row to ans.
- ans = [[1], [1, 1], [1, 2, 1], [1, 3, 3, 1]].

6. Iteration 4:
- r = 4: Create row = [1, 1, 1, 1, 1].
- Inner loop: c = 1, calculate row[1] = ans[3][0] + ans[3][1] = 1 + 3 = 4.
- Inner loop: c = 2, calculate row[2] = ans[3][1] + ans[3][2] = 3 + 3 = 6.
- Inner loop: c = 3, calculate row[3] = ans[3][2] + ans[3][3] = 3 + 1 = 4.
- row = [1, 4, 6, 4, 1].
- Add row to ans.
- ans = [[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]].

### Time Complexity

- The outer loop runs numRows times.
- The inner loop runs r times for each r from 1 to numRows - 1.
- The total number of operations is the sum of the first numRows integers, which is \(\sum_{r=1}^{numRows} r = \frac{numRows \times (numRows + 1)}{2}\).
- Thus, the time complexity is \(O(numRows^2)\).

### Space Complexity

- We store the results in a 2D vector ans.
- The total number of elements in ans is \(\sum_{r=1}^{numRows} r = \frac{numRows \times (numRows + 1)}{2}\).
- Thus, the space complexity is \(O(numRows^2)\).

twoSum #leetcode1
#Problem Statement
Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

### Solution Approach
1. Initialize a Hash Map: Create an unordered map to store the numbers and their indices.
2. Iterate through the Array: Loop through each element in the array.
3. Check for Complement: For each element, calculate the complement (target - current element).
4. Find in Hash Map: Check if the complement exists in the hash map.
- If it does, return the indices.
- If it doesn't, store the current element and its index in the hash map.
5. Return Indices: Once the complement is found, the solution is returned.

twoSum

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> mp;
        vector<int> ans;
        
        for(int i = 0; i < nums.size(); i++) {
            int complement = target - nums[i];
            
            if (mp.find(complement) != mp.end()) {
                ans.push_back(mp[complement]);
                ans.push_back(i);
                break;
            }
            mp[nums[i]] = i;
        }
        
        return ans;
    }
};

### Loop-wise Iteration

1. Initialization:
- unordered_map<int, int> mp: This will store the value and its index from nums.
- vector<int> ans: This will store the indices of the two numbers that add up to the target.

2. First Iteration (i = 0):
- nums[i] = 2
- complement = target - nums[i] = 13 - 2 = 11
- mp.find(complement) returns mp.end() because 11 is not in mp.
- mp[nums[i]] = i updates mp to {2: 0}.

3. Second Iteration (i = 1):
- nums[i] = 4
- complement = target - nums[i] = 13 - 4 = 9
- mp.find(complement) returns mp.end() because 9 is not in mp.
- mp[nums[i]] = i updates mp to {2: 0, 4: 1}.

4. Third Iteration (i = 2):
- nums[i] = 7
- complement = target - nums[i] = 13 - 7 = 6
- mp.find(complement) returns mp.end() because 6 is not in mp.
- mp[nums[i]] = i updates mp to {2: 0, 4: 1, 7: 2}.

5. Fourth Iteration (i = 3):
- nums[i] = 8
- complement = target - nums[i] = 13 - 8 = 5
- mp.find(complement) returns mp.end() because 5 is not in mp.
- mp[nums[i]] = i updates mp to {2: 0, 4: 1, 7: 2, 8: 3}.

6. Fifth Iteration (i = 4):
- nums[i] = 6
- complement = target - nums[i] = 13 - 6 = 7
- mp.find(complement) finds 7 in mp with the value 2.
- The complement 7 is found in mp, so we push back mp[complement] (which is 2) and i (which is 4) to ans.
- ans is now {2, 4}.

7. Termination:
- The loop breaks as soon as the pair is found.
- The function returns ans which is {2, 4}.

### Summary

- The unordered map mp is used to store the indices of previously visited elements.
- For each element, it checks if the complement (i.e., target - nums[i]) is already in the map.
- If the complement is found, it returns the indices of the current element and the complement.
- This approach ensures a time complexity of \(O(n)\) as each element is processed once and map operations (insertion and lookup) are average \(O(1)\).

### Time and Space Complexity

Time Complexity: O(n)
- The loop runs n times, where n is the number of elements in the nums vector.
- The find and insertion operations in an unordered map (hash map) are O(1) on average.
- Therefore, the overall time complexity is O(n).

Space Complexity: O(n)
- In the worst case, all elements could be stored in the hash map, leading to an additional space requirement of O(n).
- The space used by the result vector ans is constant (O(2) = O(1)), as it always stores exactly two indices.
- Thus, the overall space complexity is O(n).

Rotate Array #leetcode189 # Problem Statement:

Given an integer array nums, rotate the array to the right by k steps, where k is non-negative.

Example 1:

Input: nums = [1,2,3,4,5,6,7], k = 3
Output: [5,6,7,1,2,3,4]
Explanation:
rotate 1 step to the right: [7,1,2,3,4,5,6]
rotate 2 steps to the right: [6,7,1,2,3,4,5]
rotate 3 steps to the right: [5,6,7,1,2,3,4]

Example 2:

Input: nums = [-1,-100,3,99], k = 2
Output: [3,99,-1,-100]
Explanation:
rotate 1 step to the right: [99,-1,-100,3]
rotate 2 steps to the right: [3,99,-1,-100]

Constraints:
- \(1 \leq \text{nums.length} \leq 10^5\)
- \(-2^{31} \leq \text{nums[i]} \leq 2^{31} - 1\)
- \(0 \leq k \leq 10^5\)

### Solution Approach

To rotate the array to the right by k steps:
1. Normalize k: If k is greater than the length of the array, we take k % n (where n is the length of the array) because rotating by n or more steps brings us back to a previous state.
2. Reverse the Entire Array: This sets up the rotation by moving elements from the end to the beginning.
3. Reverse the First k Elements: This places the k elements that were moved to the start in their correct positions.
4. Reverse the Remaining Elements: This places the remaining elements in their correct positions.

### Code Implementation

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        k %= nums.size(); // Normalize k
        reverse(nums.begin(), nums.end()); 
        reverse(nums.begin(), nums.begin() + k); // Step 2: Reverse the first k elements
        reverse(nums.begin() + k, nums.end()); 
    }
};

### Step-by-Step Iteration with Explanation

Let's walk through the process for the input nums = [1,2,3,4,5,6,7] and k = 3.

1. Normalize k:

   k %= nums.size(); // k = 3 % 7 = 3
   

2. Reverse the Entire Array:

   reverse(nums.begin(), nums.end()); // nums becomes [7,6,5,4,3,2,1]
   

3. Reverse the First k Elements:

   reverse(nums.begin(), nums.begin() + k); // nums becomes [5,6,7,4,3,2,1]
   

4. Reverse the Remaining Elements:

   reverse(nums.begin() + k, nums.end()); // nums becomes [5,6,7,1,2,3,4]
   

### Time Complexity

- Normalizing k: O(1)
- Reversing the entire array: O(n)
- Reversing the first k elements: O(k)
- Reversing the remaining n-k elements: O(n-k)

Total time complexity is O(n) because each element is reversed exactly once.

### Space Complexity

The space complexity is O(1) because the algorithm only uses a constant amount of extra space regardless of the input size.

This approach efficiently rotates the array using a three-step reversal process, making it both time and space efficient.

### Problem Statement: Rotate Array

Given an integer array nums, rotate the array to the right by k steps, where k is non-negative.

Example 1:

- Input: nums = [1,2,3,4,5,6,7], k = 3
- Output: [5,6,7,1,2,3,4]

Example 2:

- Input: nums = [-1,-100,3,99], k = 2
- Output: [3,99,-1,-100]

Constraints:

- 1 <= nums.length <= 10^5
- -2^31 <= nums[i] <= 2^31 - 1
- 0 <= k <= 10^5

### Solution Approach

The approach used in the provided code is efficient and leverages array reversal to achieve the rotation in-place.

Steps:

1. Reverse the entire array.
2. Reverse the first k elements.
3. Reverse the remaining n-k elements.

This approach ensures that the array is rotated correctly with O(n) time complexity and O(1) space complexity.

Code:

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        k %= nums.size();
        reverse(nums.begin(), nums.end());
        reverse(nums.begin(), nums.begin() + k);
        reverse(nums.begin() + k, nums.end());
    }
};

### Loop-wise Iteration Explanation

Let's go through the example nums = [1, 2, 3, 4, 5, 6, 7] and k = 3.

Initial Array:

[1, 2, 3, 4, 5, 6, 7]

1. Reverse the entire array:

reverse(nums.begin(), nums.end());

After reversing the entire array, we get:

[7, 6, 5, 4, 3, 2, 1]

2. Reverse the first `k` elements:

reverse(nums.begin(), nums.begin() + k);

Here, k = 3, so we reverse the first three elements:

[5, 6, 7, 4, 3, 2, 1]

3. Reverse the remaining `n-k` elements:

reverse(nums.begin() + k, nums.end());

Here, we reverse the elements from index 3 to the end:

[5, 6, 7, 1, 2, 3, 4]

Final Rotated Array:

[5, 6, 7, 1, 2, 3, 4]

### Time and Space Complexity

Time Complexity:

- The reversing operation takes O(n) time.
- We perform the reverse operation three times.
- Hence, the overall time complexity is O(n).

Space Complexity:

- The algorithm uses constant extra space, i.e., O(1).

### Detailed Iteration for Each Step

#### Step 1: Reverse the Entire Array

Before reversing:

Index:  0  1  2  3  4  5  6
Array: [1, 2, 3, 4, 5, 6, 7]

After reversing:

Index:  0  1  2  3  4  5  6
Array: [7, 6, 5, 4, 3, 2, 1]

#### Step 2: Reverse the First k Elements

Before reversing the first k elements:

Index:  0  1  2  3  4  5  6
Array: [7, 6, 5, 4, 3, 2, 1]

After reversing the first k (3) elements:

Index:  0  1  2  3  4  5  6
Array: [5, 6, 7, 4, 3, 2, 1]

#### Step 3: Reverse the Remaining n-k Elements

Before reversing the remaining n-k elements:

Index:  0  1  2  3  4  5  6
Array: [5, 6, 7, 4, 3, 2, 1]

After reversing the remaining n-k (4) elements:

Index:  0  1  2  3  4  5  6
Array: [5, 6, 7, 1, 2, 3, 4]

This is how the algorithm efficiently rotates the array.

Sure, let's walk through the nextPermutation function step by step with a visual representation for better understanding.

### Code Recap

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int n = nums.size(), i, j;
        
        // Step 1: Find the first decreasing element
        for (i = n - 2; i >= 0; --i) {
            if (nums[i] < nums[i + 1]) break;
        }
        
        // Step 2: Find the element just larger than nums[i]
        if (i >= 0) {
            for (j = n - 1; j > i; --j) {
                if (nums[j] > nums[i]) break;
            }
            // Step 3: Swap elements at i and j
            std::swap(nums[i], nums[j]);
        }
        
        // Step 4: Reverse the sub-array from i + 1 to the end
        std::reverse(nums.begin() + i + 1, nums.end());
    }
};

### Initial Input
Let's use the array nums = [1, 2, 3] as an example.

### Iteration Steps

1. Initial Array: [1, 2, 3]

#### Step 1: Find the first decreasing element
- We start from the second last element and move left.
- nums[1] < nums[2] (2 < 3), so i = 1.

Current state:

  [1, 2, 3]
      ^
      i
  

#### Step 2: Find the element just larger than nums[i]
- Traverse from the last element to i.
- nums[2] > nums[1] (3 > 2), so j = 2.

Current state:

  [1, 2, 3]
      ^  ^
      i  j
  

#### Step 3: Swap nums[i] and nums[j]
- Swap nums[1] and nums[2].

After Swap:

  [1, 3, 2]
      ^  ^
      i  j
  

#### Step 4: Reverse the sub-array from i + 1 to the end
- Reverse the sub-array from i + 1 to the end ([2]).

Final State:

  [1, 3, 2]
  

### Visualization of Iterations

#### Initial Array:

[1, 2, 3]

#### Finding the first decreasing element:

[1, 2, 3]  (2 < 3, so i = 1)
    ^

#### Finding the element just larger than nums[i]:

[1, 2, 3]  (3 > 2, so j = 2)
    ^  ^

#### Swapping elements at i and j:

[1, 3, 2]
    ^  ^

#### Reversing the sub-array from i + 1 to end:

[1, 3, 2]

### Explanation of Edge Cases
1. If the array is in descending order (e.g., [3, 2, 1]), the next permutation is the smallest permutation, which is the array sorted in ascending order.
2. If the array is in ascending order (e.g., [1, 2, 3]), the next permutation swaps the last two elements to get [1, 3, 2].

### Time and Space Complexity
- Time Complexity: O(n) where n is the number of elements in the array. This is because each step involves a single pass through the array.
- Space Complexity: O(1) since no extra space proportional to the input size is used.

I hope this detailed step-by-step explanation helps you understand the problem and solution better!