Circus tower sorting
MediumUpdated: Oct 12, 2025
Problem
A circus is designing a tower routine consisting of people standing atop one another’s shoulders. For practical and aesthetic reasons, each person must be both shorter and lighter than the person below him or her. Given the heights and weights of each person in the circus, write a method to compute the largest possible number of people in such a tower.
Examples
Example 1
Input: heights = [65, 70, 56, 75, 60, 68], weights = [100, 150, 90, 200, 95, 110]
Output: 4
Explanation:
One possible tower:
(56, 90) -> (60, 95) -> (65, 100) -> (68, 110).
Height and weight strictly increase in this sequence.
Example 2
Input: heights = [50, 60, 51, 70], weights = [100, 150, 90, 200]
Output: 3
Explanation:
One possible tower:
(50, 100) -> (60, 150) -> (70, 200).
Solution
Method 1 - Sorting + LIS
The problem is essentially finding the [Longest Increasing Subsequence (LIS)](longest-common-subsequence-lcs-1-get-length) based on both height and weight. By sorting people by one attribute (height or weight) and applying LIS on the other attribute, you can determine the maximum number of people in the tower that satisfy both conditions.
So, here is the approach:
- Combine the heights and weights into pairs of
(height, weight). - Sort these pairs using height as the primary key and weight as the secondary key. 1. This ensures that if heights are distinct, the sorting will be based purely on height, while for identical heights, weights will determine the order. For instance, prior to sorting: A(60, 100), B(70, 150), C(56, 90), D(75, 190), E(60, 95), F(68, 110). After sorting, the order becomes: C(56, 90), E(60, 95), A(60, 100), F(68, 110), B(70, 150), D(75, 190).
- Apply LIS on the weights to find the longest subsequence where weights are increasing.
- Start from the beginning of the sorted list with an empty
max_sequence. If any item's height or weight is not greater than the previous item's, it is marked as "unfit" (e.g., (60, 95), (65, 100), (75, 80) → unfit item, (80, 100)). If the current sequence has more items than themax_sequence, it replaces it. Resume the search from the "unfit item" and continue until reaching the end of the list.
- Start from the beginning of the sorted list with an empty
Code
C++
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
int maxPeopleInTower(vector<int>& heights, vector<int>& weights) {
int n = heights.size();
vector<pair<int, int>> people;
// Combine heights and weights into pairs
for (int i = 0; i < n; i++) {
people.push_back({heights[i], weights[i]});
}
// Sort based on height, and break ties by weight
sort(people.begin(), people.end(), [](pair<int, int>& a, pair<int, int>& b) {
if (a.first == b.first)
return a.second < b.second;
return a.first < b.first;
});
// Find LIS based on weights
vector<int> dp(n, 1); // Each person can be a tower on their own
int maxTower = 1;
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (people[i].second > people[j].second) {
dp[i] = max(dp[i], dp[j] + 1);
}
}
maxTower = max(maxTower, dp[i]);
}
return maxTower;
}
};
int main() {
vector<int> heights = {65, 70, 56, 75, 60, 68};
vector<int> weights = {100, 150, 90, 200, 95, 110};
Solution solution;
cout << solution.maxPeopleInTower(heights, weights) << endl; // Output: 4
return 0;
}
Go
package main
import (
"fmt"
"sort"
)
type Person struct {
Height int
Weight int
}
func maxPeopleInTower(heights []int, weights []int) int {
n := len(heights)
people := make([]Person, n)
// Combine heights and weights into pairs
for i := 0; i < n; i++ {
people[i] = Person{Height: heights[i], Weight: weights[i]}
}
// Sort based on height, and break ties by weight
sort.Slice(people, func(i, j int) bool {
if people[i].Height == people[j].Height {
return people[i].Weight < people[j].Weight
}
return people[i].Height < people[j].Height
})
// Find LIS based on weights
dp := make([]int, n)
for i := range dp {
dp[i] = 1
}
maxTower := 1
for i := 1; i < n; i++ {
for j := 0; j < i; j++ {
if people[i].Weight > people[j].Weight {
dp[i] = max(dp[i], dp[j] + 1)
}
}
maxTower = max(maxTower, dp[i])
}
return maxTower
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
func main() {
heights := []int{65, 70, 56, 75, 60, 68}
weights := []int{100, 150, 90, 200, 95, 110}
result := maxPeopleInTower(heights, weights)
fmt.Println(result) // Output: 4
}
Java
public class Solution {
public static int maxPeopleInTower(int[] heights, int[] weights) {
// Combine heights and weights into pairs
int n = heights.length;
int[][] people = new int[n][2];
for (int i = 0; i < n; i++) {
people[i][0] = heights[i];
people[i][1] = weights[i];
}
// Sort based on height, and break ties by weight
Arrays.sort(people, (a, b) -> {
if (a[0] == b[0]) return a[1] - b[1];
return a[0] - b[0];
});
// Find LIS based on weights
int[] dp = new int[n];
Arrays.fill(dp, 1); // Each person can be a tower on their own
int maxTower = 1;
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (people[i][1] > people[j][1]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
maxTower = Math.max(maxTower, dp[i]);
}
return maxTower;
}
public static void main(String[] args) {
int[] heights = {65, 70, 56, 75, 60, 68};
int[] weights = {100, 150, 90, 200, 95, 110};
System.out.println(maxPeopleInTower(heights, weights)); // Output: 4
}
}
Kotlin
class Solution {
fun maxPeopleInTower(heights: IntArray, weights: IntArray): Int {
val people = heights.indices.map { i -> Pair(heights[i], weights[i]) }
// Sort based on height, and break ties by weight
val sortedPeople = people.sortedWith(compareBy({ it.first }, { it.second }))
// Find LIS based on weights
val dp = IntArray(people.size) { 1 }
var maxTower = 1
for (i in 1 until people.size) {
for (j in 0 until i) {
if (sortedPeople[i].second > sortedPeople[j].second) {
dp[i] = maxOf(dp[i], dp[j] + 1)
}
}
maxTower = maxOf(maxTower, dp[i])
}
return maxTower
}
}
fun main() {
val heights = intArrayOf(65, 70, 56, 75, 60, 68)
val weights = intArrayOf(100, 150, 90, 200, 95, 110)
val solution = Solution()
println(solution.maxPeopleInTower(heights, weights)) // Output: 4
}
Python
class Solution:
def maxPeopleInTower(self, heights, weights):
# Combine heights and weights into pairs
people = list(zip(heights, weights))
# Sort based on height, and break ties by weight
people.sort(key=lambda x: (x[0], x[1]))
# Find LIS based on weights
n = len(people)
dp = [1] * n # Each person can be a tower on their own
max_tower = 1
for i in range(1, n):
for j in range(i):
if people[i][1] > people[j][1]: # Check weight condition
dp[i] = max(dp[i], dp[j] + 1)
max_tower = max(max_tower, dp[i])
return max_tower
# Example usage
if __name__ == "__main__":
heights = [65, 70, 56, 75, 60, 68]
weights = [100, 150, 90, 200, 95, 110]
solution = Solution()
print(solution.maxPeopleInTower(heights, weights)) # Output: 4
Rust
struct Solution;
impl Solution {
fn max_people_in_tower(heights: Vec<i32>, weights: Vec<i32>) -> i32 {
let n = heights.len();
let mut people: Vec<(i32, i32)> = heights
.into_iter()
.zip(weights.into_iter())
.collect();
// Sort based on height, and break ties by weight
people.sort_by(|a, b| {
if a.0 == b.0 {
a.1.cmp(&b.1)
} else {
a.0.cmp(&b.0)
}
});
// Find LIS based on weights
let mut dp = vec![1; n];
let mut max_tower = 1;
for i in 1..n {
for j in 0..i {
if people[i].1 > people[j].1 {
dp[i] = dp[i].max(dp[j] + 1);
}
}
max_tower = max_tower.max(dp[i]);
}
max_tower
}
}
fn main() {
let heights = vec![65, 70, 56, 75, 60, 68];
let weights = vec![100, 150, 90, 200, 95, 110];
let result = Solution::max_people_in_tower(heights, weights);
println!("{}", result); // Output: 4
}
Complexity
- ⏰ Time complexity:
O(n^2)orO(n log n)depending on whether if we use naive or binary search based dp approach- Sorting time complexity:
O(n * log(n))(sorting the people based on height and weight). - LIS time complexity:
O(n^2)(naive DP approach). - Optimised LIS time complexity (using Binary Search):
O(n * log(n)).
- Sorting time complexity:
- 🧺 Space complexity:
O(n)for storing the DP array or intermediate results.