Sort Even And Odd Indices Independently - Leetcode Solution

Problem Statement:

Given an integer array nums of length n, you want to create an array ans of length n where:

ans[i] == nums[j] if i is odd and j is odd. ans[i] == nums[j] if i is even and j is even. Return any suitable array ans.

Input: nums = [4,2,5,7] Output: [4,5,2,7] Explanation: [4,7,5,2], [4,5,2,7] and [4,7,2,5] would also have been accepted.

Approach:

We can solve this problem using two different ways:

1. Two Pointer Approach:

In this approach, we maintain two pointers, one pointing to the even index and the other pointing to the odd index. We then traverse the array again and swap the elements at the even and odd indices. This way, we sort even and odd indices independently.

Algorithm:

1. Initialize two pointers ‘i’ and ‘j’ to traversing even and odd indices respectively.
2. Traverse the array using a for loop and check if the current index is even or odd.
3. If the current index is even, swap the element at the current index with the element at the even pointer.
4. If the current index is odd, swap the element at the current index with the element at the odd pointer.
5. Increment the pointers accordingly.

Time Complexity - O(n) Space Complexity - O(1)

2. Using Two Different Arrays:

In this approach, we maintain two different arrays to store the even and odd indices, respectively. We then sort these arrays separately and merge them to form the final ans array.

Algorithm:

1. Initialize two arrays ‘even_index’ and ‘odd_index’ to store the even and odd index elements respectively.
2. Traverse the input array and store elements at even and odd indices in their respective arrays.
3. Sort the even and odd index arrays separately.
4. Merge the even and odd index arrays to form the final ans array.

Time Complexity - O(n log n) for the sort Space Complexity - O(n) to store the even and odd arrays.

Solution 1: Two Pointer Approach

class Solution { public: vector<int> sortArrayByParityII(vector<int>& nums) { int i = 0, j = 1; while(i < nums.size() && j < nums.size()){ if(nums[i] % 2 == 0){ i += 2; } else if(nums[j] % 2 == 1){ j += 2; } else { swap(nums[i], nums[j]); i += 2; j += 2; } } return nums; } };

Solution 2: Using Two Different Arrays

class Solution { public: vector<int> sortArrayByParityII(vector<int>& nums) { vector<int> even_index, odd_index; for(int i = 0; i < nums.size(); i++){ if(i % 2 == 0 && nums[i] % 2 == 0){ continue; } else if(i % 2 == 1 && nums[i] % 2 == 1){ continue; } else if(i % 2 == 0 && nums[i] % 2 == 1){ odd_index.push_back(nums[i]); } else { even_index.push_back(nums[i]); } } sort(even_index.begin(), even_index.end()); sort(odd_index.begin(), odd_index.end()); vector<int> ans(nums.size()); for(int i = 0; i < nums.size(); i++){ if(i % 2 == 0){ ans[i] = even_index[i/2]; } else { ans[i] = odd_index[i/2]; } } return ans; } };

1