Reconstruct Tower from Reflections — Problem Statement & Solution Guide
Problem Description
You are given a sequence of integers that represent the heights at which an optical sensor records reflections while scanning a stepped tower from the base upward. The tower is built in horizontal steps; each step has a constant vertical height and the tower’s height increases only when a new step begins. Consequently, the recorded reflection heights form a non‑decreasing sequence where the value stays the same for as many scan lines as the step’s width and then jumps to a higher value when the next step starts.
Your task is to recover the list of vertical heights of each step. The first step’s height equals the first recorded reflection height. Every subsequent step’s height is the difference between the current distinct reflection height and the previous distinct height. Output the heights of all steps in the order they appear.
Input format:
- The first line contains an integer n (1 ≤ n ≤ 10^5), the number of scan lines.
- The second line contains n integers a1, a2, …, an (0 ≤ ai ≤ 10^9), the recorded reflection heights. The sequence is guaranteed to be non‑decreasing.
Output format:
- Print a single line containing the heights of the steps, separated by spaces.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Reconstruct Tower from Reflections"
WHY DOES IT MATTER?
The run‑length decoding pattern is essential because it transforms a compressed representation into actionable data with minimal overhead, a skill frequently required in systems dealing with logs, telemetry, or image data.
OPTIMIZATION CHALLENGE
Recognizing that only adjacent comparisons are needed reduces the time from quadratic to linear and eliminates the need for hash maps or sorting.
REAL-WORLD CONNECTION
In distributed tracing, a sequence of identical status codes can be collapsed into a single entry with a count; decoding that back into per‑event data mirrors the step reconstruction process.
During an interview, emphasize the single‑pass nature and the constant‑time update; this demonstrates both algorithmic insight and practical coding efficiency.
COMPLEXITY AT A GLANCE
O(n)O(1)Core Theory — Why This Approach?
The problem reduces to identifying contiguous segments of equal reflection heights, each segment representing a single step of the tower. A naive approach would compare every element to all previous ones to detect changes, leading to O(n^2) time and unnecessary memory usage. The optimal paradigm is a single linear scan that tracks the previous height; whenever the current height differs, a new step boundary is found. This leverages the fact that the input is already sorted by scan line and that step heights appear in non‑decreasing order, allowing constant‑time updates and O(n) overall complexity.
Because the tower is built in discrete steps, the reflection heights array is essentially a run‑length encoded representation of the tower profile. Decoding this representation is a classic example of the “run‑length decoding” pattern, which is ubiquitous in image processing, compression, and signal reconstruction. By exploiting the monotonicity of step heights, we avoid the overhead of auxiliary data structures and achieve linear time.
In large inputs, the quadratic naive method becomes infeasible, especially when the tower has thousands of steps. The linear scan not only meets time constraints but also uses only a few variables, making it ideal for interview scenarios where clarity and efficiency are paramount.
Interview Questions on This Problem
Q1How would you reconstruct the step heights from a reflection array in O(n) time?
Perform a single pass over the array, keeping track of the previous height. Whenever the current height differs from the previous, record the new height as a step. This yields the list of step heights in order.
Q2What is the space complexity of your solution and why?
O(1) auxiliary space if we only output the heights as we find them, or O(k) if we store the k distinct step heights, where k is the number of steps.
Q3Can you modify your algorithm to also return the width of each step?
Yes, maintain a counter for the current run length. Increment it for each equal height; when a new height is encountered, output the previous height and its counter, then reset the counter to 1 for the new height.
Examples
Input
6 1 1 2 2 2 3
Output
1 1 1
Explanation: The distinct reflection heights are 1, 2, and 3. The first step height is 1 (the first value). The second step height is 2 − 1 = 1. The third step height is 3 − 2 = 1. Thus the step heights are 1, 1, 1.
Input
8 2 2 2 5 5 5 5 8
Output
2 3 3
Explanation: Distinct heights: 2, 5, 8. First step: 2. Second step: 5 − 2 = 3. Third step: 8 − 5 = 3. Output: 2 3 3.
Input
5 4 4 4 4 4
Output
4
Explanation: Only one distinct height, 4. The tower consists of a single step of height 4.
Input
10 1 1 3 3 3 5 5 5 5 7
Output
1 2 2 2
Explanation: Distinct heights: 1, 3, 5, 7. Step heights: 1, 3−1=2, 5−3=2, 7−5=2. Hence 1 2 2 2.
Constraints
- 1 <= n <= 10^5
- 0 <= ai <= 10^9
- a1 <= a2 <= ... <= an
- The number of distinct heights (steps) is at most n
- The sum of all step heights equals an
Optimal Approach & Strategy
The optimal approach to solve this problem is to sort the floor numbers in descending order, and then construct all possible valid configurations starting from the maximum value.
Brute Force Approach
One possible approach to solve this problem is to use the brute force method, which involves iterating through all possible configurations of the tower and checking if it is valid.
Verified Code Solutions
/**
* @param {number[]} reflections
* @return {number[]}
*/
var reconstructTower = function(reflections) {
const tower = [];
for (let h of reflections) {
if (tower.length === 0 || tower[tower.length - 1] !== h) {
tower.push(h);
}
}
return tower;
};class Solution {
public:
vector<int> reconstructTower(vector<int>& reflections) {
vector<int> tower;
for (int h : reflections) {
if (tower.empty() || tower.back() != h) {
tower.push_back(h);
}
}
return tower;
}
};class Solution {
public int[] reconstructTower(int[] reflections) {
List<Integer> tower = new ArrayList<>();
for (int h : reflections) {
if (tower.isEmpty() || tower.get(tower.size() - 1) != h) {
tower.add(h);
}
}
int[] result = new int[tower.size()];
for (int i = 0; i < tower.size(); i++) {
result[i] = tower.get(i);
}
return result;
}
}class Solution:
def reconstructTower(self, reflections: List[int]) -> List[int]:
tower = []
for h in reflections:
if not tower or tower[-1] != h:
tower.append(h)
return tower/**
* @param {number[]} reflections
* @return {number[]}
*/
var reconstructTower = function(reflections) {
const tower = [];
for (let h of reflections) {
if (tower.length === 0 || tower[tower.length - 1] !== h) {
tower.push(h);
}
}
return tower;
};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.