Rearrange Seats by Rating — Problem Statement & Solution Guide
Problem Description
Rearrange the seats such that the highest ratings are at the center and the lower ratings are towards the sides. Specifically, seats at odd indices should have higher ratings than seats at even indices. If there is an odd number of seats, the middle seat should have the highest rating.
Examples
Input
[5, 4, 3, 2, 1]
Output
[5, 4, 3, 2, 1]
Explanation: Step-by-step: Sort the array in descending order. Then, alternate between the highest and lowest ratings at odd and even indices respectively. For an array of length n, the first n/2 elements will be from the sorted array in descending order, and the remaining n/2 elements will be from the sorted array in ascending order.
Input
[10, 9, 8, 7, 6]
Output
[10, 9, 8, 7, 6]
Explanation: Step-by-step: Sort the array in descending order. Then, alternate between the highest and lowest ratings at odd and even indices respectively. For an array of length n, the first n/2 elements will be from the sorted array in descending order, and the remaining n/2 elements will be from the sorted array in ascending order.
Constraints
- The input array is never empty
- The total number of seats is within the range 2 <= n <= 2*10^5
- All seats in the input array are unique, and the ratings are guaranteed to be non-negative
- The ratings of seats can be the same
- If there are an odd number of seats, the middle seat should have a higher rating.
Optimal Approach & Strategy
The optimized approach involves sorting the seats based on their popularity and then using a two-pointer approach to rearrange the seats in O(n log n) time complexity.
Brute Force Approach
The brute force approach involves trying all possible permutations of the seats and checking if the current permutation satisfies the condition.
Verified Code Solutions
function rearrangeSeats(seats) { if (seats.length === 0) return seats; seats.sort((a, b) => b - a); let result = new Array(seats.length); let small = 0, large = seats.length - 1; for (let i = 0; i < seats.length; i++) { if (i % 2 === 0) result[i] = seats[large--]; else result[i] = seats[small++]; } // Correct the last element if (seats.length % 2 === 1) { result[seats.length - 1] = seats[large]; } return result; }class Solution {
public int[] solution(int[] ratings) {
// Sort the array in descending order
Arrays.sort(ratings);
int n = ratings.length;
int[] result = new int[n];
// Alternate between the highest and lowest ratings at odd and even indices respectively
for (int i = 0; i < n; i++) {
if (i % 2 == 0) {
result[i] = ratings[n - 1 - i / 2];
} else {
result[i] = ratings[i / 2];
}
}
return result;
}
}def solution(ratings):
# Sort the array in descending order
ratings.sort(reverse=True)
n = len(ratings)
result = []
# Alternate between the highest and lowest ratings at odd and even indices respectively
for i in range(n):
if i % 2 == 0:
result.append(ratings.pop())
else:
result.append(ratings.pop(0))
return resultfunction rearrangeSeats(seats) { if (seats.length === 0) return seats; seats.sort((a, b) => b - a); let result = new Array(seats.length); let small = 0, large = seats.length - 1; for (let i = 0; i < seats.length; i++) { if (i % 2 === 0) result[i] = seats[large--]; else result[i] = seats[small++]; } // Correct the last element if (seats.length % 2 === 1) { result[seats.length - 1] = seats[large]; } return result; }Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.