// Time complexity : O(N), N is length of nums array
// Space complexity : O(1)
class Solution {
    public int[] sortArrayByParityII(int[] nums) {
        int n = nums.length;
//         take two pointers, one at start and another at end
        int lo = 0, hi = n-1;
        while(lo < n && hi>=0){
//             problem can exist at any pointer if index is odd and num is even and vice versa 
            while(lo < n && (lo %2 == 0 && (nums[lo] % 2 == 0) || (lo %2 != 0 && nums[lo] % 2 != 0))){
//                 increament 2 because next odd or even index is 2 places ahead
                lo += 2;
            }
            while(hi >= 0 && ((hi %2 == 0 && nums[hi] % 2 == 0) || (hi %2 != 0 && nums[hi] % 2 != 0))){
// decreament 2 because next odd or even index is 2 places before
                hi -= 2;
            }
//             if lo and hi are within range then swap them
            if(lo < n && hi >= 0){
                int temp = nums[lo];
                nums[lo] = nums[hi];
                nums[hi] = temp;
                lo += 2;
                hi -= 2;
            }
        }
       return nums;
    }
}
//another approach could be 
class Solution {
    public int[] sortArrayByParityII(int[] nums) {
        int n = nums.length;
        
        int lo = 0, hi = 1;
        while(lo < n && hi<n){
            while(lo < n && (lo %2 == 0 && (nums[lo] % 2 == 0) || (lo %2 != 0 && nums[lo] % 2 != 0))){
                lo += 2;
            }
            while(hi <n && ((hi %2 == 0 && nums[hi] % 2 == 0) || (hi %2 != 0 && nums[hi] % 2 != 0))){
                hi += 2;
            }
            if(lo < n && hi < n){
                int temp = nums[lo];
                nums[lo] = nums[hi];
                nums[hi] = temp;
                lo += 2;
                hi += 2;
            }
        }
       return nums;
    }
}