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

1
2
3
4
5
6
7
8

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

1
2
3
4
5
6

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) 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:

  1. Combine the heights and weights into pairs of (height, weight).
  2. 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).
  3. Apply LIS on the weights to find the longest subsequence where weights are increasing.
    1. 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 the max_sequence, it replaces it. Resume the search from the “unfit item” and continue until reaching the end of the list.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

#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;
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

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
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

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
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

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
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

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
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

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) or O(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)).
  • 🧺 Space complexity: O(n) for storing the DP array or intermediate results.