【Video】How we think about a solution - One Pointer - Python, JavaScript, Java, C++
Welcome to my article! This artcle starts with "How we think about a solution". In other words, that is my thought process to solve the question. This article e
Welcome to my article! This artcle starts with "How we think about a solution". In other words, that is my thought process to solve the question. This article explains how I get to my solution instead of just posting solution codes or out of blue algorithms. I hope this aricle is helpful for someone.

# Intuition
Keep the next swapping place with left pointer for even number.

---

# Solution Video

https://youtu.be/Lxer4SbVaKY

■ Timeline of the video
`0:00` Read the question of Sort Array By Parity
`0:14` How we think about a solution
`0:42` Demonstrate solution with an example.
`2:47` Coding
`3:50` Time Complexity and Space Complexity

### ⭐️⭐️ Don't forget to subscribe to my channel! ⭐️⭐️

**■ Subscribe URL**
http://www.youtube.com/channel/UC9RMNwYTL3SXCP6ShLWVFww?sub_confirmation=1

Subscribers: 2,515
My initial goal is 10,000
Thank you for your support!

---

# Approach

### How we think about a solution

This question is very simple. We just move all the even integers to the left side of array. That's why we need to have left pointer that indicates the next swapping place when we find the next even integer.

```
Input: nums = [3,1,2,4]
left = 0
```
Now we have the left pointer at index 0. Iterate through the input array one by one.

```
Found 3
is 3 even? → No, just move next.
left = 0
```
```
Found 1
is 1 even? → No, just move next.
left = 0
```
Here is an interesting point.
```
Found 2
is 2 even? → Yes, let's swap 2 and the number at index 0(left pointer)

Now
array: [2,1,3,4]
left = 1
```
**When we swap the two numbers, we know that current number at the left pointer is an even number**, so we should move the left pointer to next. In this case we move the left pointer from `0` to `1`.

```
Found 4
is 4 even? → Yes, let's swap 4 and the number at index 0(left pointer)

Now
array: [2,4,3,1]
left = 2
```
The same reason above.

All we have to do is just return array `[2,4,3,1]`. This question accepts any order if we satisfy the condition.

Acutually, we can apply the same idea to `Move Zeroes` problem. I solved it about a year ago.

https://youtu.be/BPb0q5J4u-k


Let's see a real algorithm of this question.

### Algorithm Overview:

1. Initialize a variable `left` to 0.
2. Iterate through the input list `nums` and for each element:
   - If the element is even (divisible by 2), swap it with the element at index `left` and increment `left`.

### Detailed Explanation:

1. Initialize a variable `left` to 0. This variable will keep track of the position to which even numbers will be moved.

2. Iterate through the input list `nums` using a for loop with index `i`:
   - Check if the current element `nums[i]` is even (i.e., divisible by 2) by using the modulus operator (%). If `nums[i]` is even:
     - Swap the current element `nums[i]` with the element at index `left` in the `nums` array.
     - Increment the `left` variable by 1, effectively moving the even number to its correct position on the left side of the array.

3. Repeat step 2 for each element in the `nums` array.

4. Return the modified `nums` array, which now has even numbers grouped on the left side and odd numbers on the right side.


---


# Complexity

### Time Complexity: $$O(n)$$

`n` is the length of the input list `nums`. This is because the code iterates through the input list once, performing constant-time operations for each element (swapping and updating the `left` pointer). The number of operations is directly proportional to the length of the input list.

### Space Complexity: $$O(1)$$

$$O(1)$$ is indicating constant space usage. The algorithm doesn't use any extra data structures that grow with the input size. The space used is independent of the input size and is mainly occupied by a few variables (`left`, `i`) used for bookkeeping during the iteration.

```python []
class Solution:
    def sortArrayByParity(self, nums: List[int]) -> List[int]:
        left = 0

        for i in range(len(nums)):
            if nums[i] % 2 == 0:
                nums[left], nums[i] = nums[i], nums[left]
                left += 1
        
        return nums
```
```javascript []
/**
 * @param {number[]} nums
 * @return {number[]}
 */
var sortArrayByParity = function(nums) {
    let left = 0;

    for (let i = 0; i < nums.length; i++) {
        if (nums[i] % 2 === 0) {
            [nums[left], nums[i]] = [nums[i], nums[left]];
            left++;
        }
    }

    return nums;    
};
```
```java []
class Solution {
    public int[] sortArrayByParity(int[] nums) {
        int left = 0;

        for (int i = 0; i < nums.length; i++) {
            if (nums[i] % 2 == 0) {
                int temp = nums[left];
                nums[left] = nums[i];
                nums[i] = temp;
                left++;
            }
        }

        return nums;        
    }
}
```
```C++ []
class Solution {
public:
    vector<int> sortArrayByParity(vector<int>& nums) {
        int left = 0;

        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] % 2 == 0) {
                std::swap(nums[left], nums[i]);
                left++;
            }
        }

        return nums;        
    }
};
```

---

Thank you for reading my post.
⭐️ Please upvote it and don't forget to subscribe to my channel!

⭐️ Subscribe URL
http://www.youtube.com/channel/UC9RMNwYTL3SXCP6ShLWVFww?sub_confirmation=1

https://youtu.be/pCc4kR-TdYs
['Array', 'Two Pointers', 'Sorting', 'C++', 'Java', 'Python3']