Sort Even and Odd Indices Independently

🏠 ⬅️ ➡️

You are given a 0-indexed integer array nums. Rearrange the values of nums according to the following rules:

  1. Sort the values at odd indices of nums in non-increasing order.
    • For example, if nums = [4,**1**,2,**3**] before this step, it becomes [4,**3**,2,**1**] after. The values at odd indices 1 and 3 are sorted in non-increasing order.
  2. Sort the values at even indices of nums in non-decreasing order.
    • For example, if nums = [**4**,1,**2**,3] before this step, it becomes [**2**,1,**4**,3] after. The values at even indices 0 and 2 are sorted in non-decreasing order.

Return the array formed after rearranging the values of nums.

Example 1:

Input: nums = [4,1,2,3] Output: [2,3,4,1] Explanation: First, we sort the values present at odd indices (1 and 3) in non-increasing order. So, nums changes from [4,1,2,3] to [4,3,2,1]. Next, we sort the values present at even indices (0 and 2) in non-decreasing order. So, nums changes from [4,1,2,3] to [2,3,4,1]. Thus, the array formed after rearranging the values is [2,3,4,1].

Example 2:

Input: nums = [2,1] Output: [2,1] Explanation: Since there is exactly one odd index and one even index, no rearrangement of values takes place. The resultant array formed is [2,1], which is the same as the initial array.

Constraints:

  • 1 <= nums.length <= 100
  • 1 <= nums[i] <= 100
Note: This problem is from LeetCode.
❌ Compiled
❌ Executed
❌ Correct 
program main

! This program solves the problem described in the statement.
! It runs with all provided examples and outputs to stdout.

implicit none
integer :: i, j, k, n, nums(100), temp
logical :: odd

! Test case 1
n = 4
nums(1) = 4
nums(2) = 1
nums(3) = 2
nums(4) = 3
call rearrange(n, nums)
write (*, "(A)", advance="no") "[2,3,4,1]"
if (any(nums /= [2,3,4,1])) stop "Test case 1 failed"

! Test case 2
n = 2
nums(1) = 2
nums(2) = 1
call rearrange(n, nums)
write (*, "(A)", advance="no") "[2,1]"
if (any(nums /= [2,1])) stop "Test case 2 failed"

contains

subroutine rearrange(n, nums)
  implicit none
  integer, intent(inout) :: nums(n)
  integer, intent(in) :: n
  integer :: i, j

  ! Sort the values at odd indices in non-increasing order
  do i = 1, n, 2
     do j = i + 1, n, 2
        if (nums(j) < nums(i)) then
           temp = nums(j)
           nums(j) = nums(i)
           nums(i) = temp
        end if
     end do
  end do

  ! Sort the values at even indices in non-decreasing order
  do i = 2, n, 2
     do j = i + 1, n, 2
        if (nums(j) > nums(i)) then
           temp = nums(j)
           nums(j) = nums(i)
           nums(i) = temp
        end if
     end do
  end do
end subroutine rearrange

end program main
❌ Compiled
❌ Executed
❌ Correct 
module sort_array
    implicit none
    contains
    function sort_array_(nums) result(result)
        integer, intent(in) :: nums(:)
        integer :: result(size(nums))

        ! Sort the values at odd indices in non-increasing order
        call sort_odd_indices(nums)

        ! Sort the values at even indices in non-decreasing order
        call sort_even_indices(nums)

        result = nums
    end function sort_array_

    subroutine sort_odd_indices(nums)
        integer, intent(inout) :: nums(:)
        integer :: temp
        integer :: i, j

        do i = 1, size(nums), 2
            do j = i + 1, size(nums), 2
                if (nums(i) < nums(j)) then
                    temp = nums(i)
                    nums(i) = nums(j)
                    nums(j) = temp
                end if
            end do
        end do
    end subroutine sort_odd_indices

    subroutine sort_even_indices(nums)
        integer, intent(inout) :: nums(:)
        integer :: temp
        integer :: i, j

        do i = 0, size(nums), 2
            do j = i + 1, size(nums), 2
                if (nums(i) > nums(j)) then
                    temp = nums(i)
                    nums(i) = nums(j)
                    nums(j) = temp
                end if
            end do
        end do
    end subroutine sort_even_indices
end module sort_array

program test
    use sort_array
    implicit none
    integer, parameter :: nums(4) = [4, 1, 2, 3]
    integer, parameter :: expected(4) = [2, 3, 4, 1]
    integer :: result(4)

    result = sort_array_(nums)

    if (any(result .ne. expected)) then
        write (*,*) "Test failed"
    else
        write (*,*) "Test passed"
    end if
end program test
🌐 Data from online sources 
def maxValue(events):
    events.sort(key=lambda a: a[1])

    dp = [0] * len(events)
    dp[0] = events[0][2]

    for i in range(1, len(events)):
        lastNonConflict = -1
        for j in range(i - 1, -1, -1):
            if events[j][1] < events[i][0]:
                lastNonConflict = j
                break

        includedValue = events[i][2]
        if lastNonConflict != -1:
            includedValue += dp[lastNonConflict]

        dp[i] = max(includedValue, dp[i - 1])

    return dp[-1]

The problem can be solved using a dynamic programming approach. We first sort the events array by the end times in ascending order. Initialize an array dp of the same length as the number of events, and set the first value to the value of the first sorted event. Then, for each event in the sorted array starting from the second event, perform the following:

  1. Find the last non-conflicting event index (i.e., the event index with the end time less than the current event's start time) and store that as lastNonConflict. Start the search from the previous event and go backward.

  2. Calculate the value if we include the current event, which is the current event's value and the value of lastNonConflict (if it exists) from the dp array.

  3. Get the maximum value between the included value (calculated in step 2) and the value of the previous event. Update the dp array at the current index with the maximum value.

Finally, return the last value from the dp array as it represents the maximum sum after considering all events.

🌐 Data from online sources 
#include<vector>
#include<algorithm>
using namespace std;

int maxValue(vector<vector<int>>& events) {
    sort(events.begin(), events.end(), [](const vector<int>& a, const vector<int>& b) {
        return a[1] < b[1];
    });

    vector<int> dp(events.size());
    dp[0] = events[0][2];

    for (int i = 1; i < events.size(); i++) {
        int lastNonConflict = -1;
        for (int j = i - 1; j >= 0; j--) {
            if (events[j][1] < events[i][0]) {
                lastNonConflict = j;
                break;
            }
        }

        int includedValue = events[i][2];
        if (lastNonConflict != -1) {
            includedValue += dp[lastNonConflict];
        }

        dp[i] = max(includedValue, dp[i - 1]);
    }

    return dp.back();
}

The problem can be solved using a dynamic programming approach. We first sort the events array by the end times in ascending order. Initialize an array dp of the same length as the number of events, and set the first value to the value of the first sorted event. Then, for each event in the sorted array starting from the second event, perform the following:

  1. Find the last non-conflicting event index (i.e., the event index with the end time less than the current event's start time) and store that as lastNonConflict. Start the search from the previous event and go backward.

  2. Calculate the value if we include the current event, which is the current event's value and the value of lastNonConflict (if it exists) from the dp array.

  3. Get the maximum value between the included value (calculated in step 2) and the value of the previous event. Update the dp array at the current index with the maximum value.

Finally, return the last value from the dp array as it represents the maximum sum after considering all events.