Rearranging Theater Seating by Seat Popularity — Problem Statement & Solution Guide
Problem Description
Given an array nums of length n where each element denotes the popularity rating of a seat in a linear auditorium, produce a new ordering of the seats such that the most popular seats occupy the central positions and popularity decreases symmetrically towards the ends. Formally, sort the values in descending order and then place them in the following sequence of indices: for odd n the order is mid, mid‑1, mid+1, mid‑2, mid+2,…; for even n the order is mid‑1, mid, mid‑2, mid+1, mid‑3, mid+2,… where mid = n/2 (integer division). Output the rearranged array. The input consists of an integer n followed by n space‑separated integers; the output is a single line with the reordered n integers.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Rearranging Theater Seating by Seat Popularity"
WHY DOES IT MATTER?
This pattern—sorting then interleaving from the centre—is a reusable technique for any problem that requires a “peak‑centered” ordering, such as constructing wave arrays, arranging frequencies for audio processing, or building balanced binary search trees from sorted data.
OPTIMIZATION CHALLENGE
The key insight is to avoid costly insert‑at‑index operations by pre‑computing the exact target indices and writing directly into a fresh array, turning a potentially quadratic process into linear time after sorting.
REAL-WORLD CONNECTION
Think of a concert hall where premium tickets are sold for centre seats. The venue manager must allocate the highest‑demand tickets to the middle rows and gradually assign lower‑demand tickets outward, mirroring the algorithmic placement of values.
In an interview, write the sorting line first, then sketch the index sequence on paper (mid, mid‑1, mid+1, …). Implement the placement loop with a simple for‑loop and a toggle flag; this keeps the code clean and demonstrates clear thinking.
COMPLEXITY AT A GLANCE
O(n log n)O(n)Core Theory — Why This Approach?
The task can be reduced to a classic rearrangement problem: after sorting the seat popularity values in descending order, we must interleave them so that the largest values occupy the centre of the array and the values decrease symmetrically towards both ends. A naive solution would repeatedly insert each element at the required index using list operations, which leads to O(n^2) time on large inputs because each insertion may shift O(n) elements. The optimal paradigm leverages the fact that the sorted order is already known; by using two pointers (or a simple index sequence) we can place the elements directly into a new result array in O(n) time after the initial O(n log n) sort. This approach respects the required index pattern – for odd n the centre index is (n‑1)/2, then we fill positions alternating to the left and right, and for even n we start at n/2‑1 and n/2 – achieving the desired symmetric popularity distribution with minimal overhead.
Interview Questions on This Problem
Q1How would you rearrange seats in a theater so that the most popular seats are in the centre and popularity decreases symmetrically to the ends?
First sort the popularity ratings in descending order. Then, using two pointers, fill a new array by placing the first (largest) element at the centre, the next at centre‑1, then centre+1, then centre‑2, centre+2, and so on, handling odd/even length edge cases accordingly.
Q2What is the time and space complexity of the optimal solution for this seating‑rearrangement problem?
The dominant step is sorting, which costs O(n log n) time. The subsequent placement is O(n). Overall time complexity is O(n log n). We allocate a new array of size n, so the space complexity is O(n) (or O(1) extra if we overwrite in‑place with careful index calculations).
Q3How would you adapt the algorithm if the auditorium length is even versus odd?
For odd n, the centre index is (n‑1)/2 and we start filling from there. For even n, there are two middle positions n/2‑1 and n/2; we start with the left middle (n/2‑1) for the largest value, then the right middle for the second largest, and continue alternating outward.
Examples
Input
7 4 1 3 9 2 5 8
Output
2 4 8 9 5 3 1
Explanation: Sorted descending: [9,8,5,4,3,2,1]. Placement order for n=7 (mid=3) is indices 3,2,4,1,5,0,6. Assigning values yields positions: 3←9, 2←8, 4←5, 1←4, 5←3, 0←2, 6←1 → final array [2,4,8,9,5,3,1].
Input
6 10 20 30 40 50 60
Output
20 40 60 50 30 10
Explanation: Sorted descending: [60,50,40,30,20,10]. For even n=6, mid=n/2=3, placement order is 2,3,1,4,0,5. Mapping values gives: index2←60, index3←50, index1←40, index4←30, index0←20, index5←10 → final array [20,40,60,50,30,10].
Input
1 42
Output
42
Explanation: Only one seat; it remains at the center unchanged.
Constraints
- 1 <= n <= 100000
- 0 <= nums[i] <= 10^9
- All input values are integers
Optimal Approach & Strategy
Sort the array once, then compute the centre index and fill a new result array by walking outward with two pointers, achieving O(n) placement after the O(n log n) sort.
Brute Force Approach
Sort the array, then for each element repeatedly insert it at the required position using list insert operations, which shifts elements and leads to O(n^2) time.
Verified Code Solutions
const fs = require('fs');
const data = fs.readFileSync(0,'utf8').trim().split(/\s+/).map(Number);
let p=0;
const n = data[p++]||0;
const arr = data.slice(p,p+n);
function rearrange(nums){
const n = nums.length;
if(n===0) return [];
const sorted = [...nums].sort((a,b)=>b-a);
const res = new Array(n);
const mid = Math.floor((n-1)/2);
let idx=0;
res[mid]=sorted[idx++];
for(let offset=1; idx<n; ++offset){
if(mid-offset>=0) res[mid-offset]=sorted[idx++];
if(idx>=n) break;
if(mid+offset<n) res[mid+offset]=sorted[idx++];
}
return res;
}
const out = rearrange(arr);
console.log(out.join(' '));#include <bits/stdc++.h>
using namespace std;
vector<int> rearrange(const vector<int>& nums){
int n=nums.size();
if(n==0) return {};
vector<int> sorted=nums;
sort(sorted.begin(),sorted.end(),greater<int>());
vector<int> res(n);
int mid=(n-1)/2; // left middle for even length
int posIdx=0;
res[mid]=sorted[posIdx++];
for(int offset=1; posIdx<n; ++offset){
if(mid-offset>=0) res[mid-offset]=sorted[posIdx++];
if(posIdx>=n) break;
if(mid+offset<n) res[mid+offset]=sorted[posIdx++];
}
return res;
}
int main(){ios::sync_with_stdio(false);cin.tie(nullptr);
int n; if(!(cin>>n)) return 0; vector<int>a(n); for(int i=0;i<n;++i)cin>>a[i];
vector<int> ans=rearrange(a);
for(int i=0;i<ans.size();++i){if(i) cout<<' '; cout<<ans[i];}
cout<<"\n"; return 0;}
import java.util.*;
public class Main {
static int[] rearrange(int[] nums){
int n=nums.length;
if(n==0) return new int[0];
Integer[] boxed = new Integer[n];
for(int i=0;i<n;i++) boxed[i]=nums[i];
Arrays.sort(boxed, Collections.reverseOrder());
int[] sorted = new int[n];
for(int i=0;i<n;i++) sorted[i]=boxed[i];
int[] res = new int[n];
int mid=(n-1)/2;
int idx=0;
res[mid]=sorted[idx++];
for(int offset=1; idx<n; offset++){
if(mid-offset>=0) res[mid-offset]=sorted[idx++];
if(idx>=n) break;
if(mid+offset<n) res[mid+offset]=sorted[idx++];
}
return res;
}
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
if(!sc.hasNextInt()) return;
int n=sc.nextInt();
int[] arr=new int[n];
for(int i=0;i<n;i++) arr[i]=sc.nextInt();
int[] ans=rearrange(arr);
for(int i=0;i<ans.length;i++){
if(i>0) System.out.print(" ");
System.out.print(ans[i]);
}
System.out.println();
}
}
import sys
def rearrange(nums):
n=len(nums)
if n==0:
return []
sorted_nums=sorted(nums,reverse=True)
res=[0]*n
mid=(n-1)//2
idx=0
res[mid]=sorted_nums[idx]; idx+=1
offset=1
while idx<n:
if mid-offset>=0:
res[mid-offset]=sorted_nums[idx]; idx+=1
if idx>=n: break
if mid+offset<n:
res[mid+offset]=sorted_nums[idx]; idx+=1
offset+=1
return res
def main():
data=sys.stdin.read().strip().split()
if not data:
return
n=int(data[0])
arr=list(map(int,data[1:1+n]))
print(' '.join(map(str,rearrange(arr))))
if __name__=='__main__':
main()
const fs = require('fs');
const data = fs.readFileSync(0,'utf8').trim().split(/\s+/).map(Number);
let p=0;
const n = data[p++]||0;
const arr = data.slice(p,p+n);
function rearrange(nums){
const n = nums.length;
if(n===0) return [];
const sorted = [...nums].sort((a,b)=>b-a);
const res = new Array(n);
const mid = Math.floor((n-1)/2);
let idx=0;
res[mid]=sorted[idx++];
for(let offset=1; idx<n; ++offset){
if(mid-offset>=0) res[mid-offset]=sorted[idx++];
if(idx>=n) break;
if(mid+offset<n) res[mid+offset]=sorted[idx++];
}
return res;
}
const out = rearrange(arr);
console.log(out.join(' '));
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.