Leetcode 2164: Sort Even and Odd Indices Independently
You are given a 0-indexed integer array ’nums’. Your task is to rearrange the elements of ’nums’ by sorting the values at odd indices in non-increasing order and the values at even indices in non-decreasing order. Return the rearranged array.
Problem
Approach
Steps
Complexity
Input: The input consists of an integer array 'nums'.
Example: nums = [5, 2, 8, 1]
Constraints:
• 1 <= nums.length <= 100
• 1 <= nums[i] <= 100
Output: The output should be the array 'nums' after rearranging it according to the given sorting rules.
Example: [2, 8, 5, 1]
Constraints:
• The output must preserve the rearrangement order for odd and even indices as described.
Goal: Sort elements at odd indices in non-increasing order and elements at even indices in non-decreasing order.
Steps:
• Iterate through the array and sort the elements at even indices in non-decreasing order.
• Iterate through the array and sort the elements at odd indices in non-increasing order.
Goal: The input array nums has between 1 and 100 elements, and each element is between 1 and 100.
Steps:
• nums.length between 1 and 100
• 1 <= nums[i] <= 100
Assumptions:
• The input array will always contain between 1 and 100 elements.
• Elements are integers in the range 1 to 100.
• Input: Example 1: nums = [5, 2, 8, 1]
• Explanation: First, the elements at odd indices [2, 1] are sorted in non-increasing order to become [8, 1]. Then, the elements at even indices [5, 8] are sorted in non-decreasing order to become [2, 5]. The final array is [2, 8, 5, 1].
• Input: Example 2: nums = [9, 7]
• Explanation: There is only one element at an odd index and one at an even index, so the array remains [7, 9].
Approach: The approach involves sorting elements at odd and even indices separately while preserving their relative order.
Observations:
• Sorting odd and even indices separately ensures that the required order is maintained.
• The solution involves simple sorting and iterating through the array.
Steps:
• Sort the elements at even indices in non-decreasing order.
• Sort the elements at odd indices in non-increasing order.
Empty Inputs:
• The array must have at least one element.
Large Inputs:
• The solution should handle arrays with up to 100 elements.
Special Values:
• Arrays with all elements equal should still return the same array.
Constraints:
• The solution must handle arrays with lengths between 1 and 100 efficiently.
vector<int> sortEvenOdd(vector<int>& nums) {
int minIndex;
// Here in this nested loop , we are sorting the elements at even indices in non-decreasing order.
for(int i=0;i<nums.size();i+=2)
{
minIndex=i;
for(int j=i+2;j<nums.size();j+=2)
{
if(nums[j]<nums[minIndex])
minIndex=j;
}
swap(nums[i],nums[minIndex]);
}
// Here , we are trying to sort the elements at odd indices in non-increasing order.
for(int i=1;i<nums.size();i+=2)
{
minIndex=i;
for(int j=i+2;j<nums.size();j+=2)
{
if(nums[j]>nums[minIndex])
minIndex=j;
}
swap(nums[i],nums[minIndex]);
}
return nums;
}
1 : Function Definition
vector<int> sortEvenOdd(vector<int>& nums) {
Defines the function that takes a vector of integers as input and returns a vector of integers.
2 : Variable Initialization
int minIndex;
Initializes the variable 'minIndex' to store the index of the minimum element during the sorting process.
3 : For Loop
for(int i=0;i<nums.size();i+=2)
Loop iterates through the elements at even indices in the vector 'nums'.
4 : Assignment
minIndex=i;
Sets 'minIndex' to the current index to track the minimum element.
5 : Nested For Loop
for(int j=i+2;j<nums.size();j+=2)
Nested loop iterates over the remaining even indices starting from the next index.
6 : Comparison
if(nums[j]<nums[minIndex])
Compares the current element with the element at 'minIndex' to find the smallest element.
7 : Index Update
minIndex=j;
Updates 'minIndex' to the new index if a smaller element is found.
8 : Swap
swap(nums[i],nums[minIndex]);
Swaps the elements at index 'i' and 'minIndex' to place the smallest element at index 'i'.
9 : For Loop
for(int i=1;i<nums.size();i+=2)
Loop iterates through the elements at odd indices in the vector 'nums'.
10 : Block Start
{
Begins the block for the loop processing odd indices.
11 : Assignment
minIndex=i;
Sets 'minIndex' to the current index to track the maximum element during the sorting process.
12 : Nested For Loop
for(int j=i+2;j<nums.size();j+=2)
Nested loop iterates over the remaining odd indices starting from the next index.
13 : Comparison
if(nums[j]>nums[minIndex])
Compares the current element with the element at 'minIndex' to find the largest element.
14 : Index Update
minIndex=j;
Updates 'minIndex' to the new index if a larger element is found.
15 : Swap
swap(nums[i],nums[minIndex]);
Swaps the elements at index 'i' and 'minIndex' to place the largest element at index 'i'.
16 : Return
return nums;
Returns the sorted vector 'nums'.
Best Case: O(n^2)
Average Case: O(n^2)
Worst Case: O(n^2)
Description: The time complexity for sorting each set of indices is O(n^2).
Best Case: O(1)
Worst Case: O(1)
Description: We use constant extra space apart from the input array.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus