SDE - 1

Case 1: Product Data is Sorted by Timestamp

Approach: Binary Search. Since the data is ordered, I used std::upper_bound (in C++) to find the first element greater than the query timestamp, then moved one step back to get the “latest known price.”

Case 2: Both Product Data and Queries are Sorted

Approach: Two Pointers / Sliding Window. I maintained a pointer for the product array and iterated through the queries. Since both are sorted, the pointer only moves forward, making the lookup extremely efficient.

Case 3: Data is Unsorted

Approach: Pre-processing. I first sorted the product array by timestamp (O(N log N)) and then applied the Binary Search or Two-Pointer method, depending on whether the query vector was also sorted.

Sorting Strategy: I first sorted the envelopes by width in ascending order. For envelopes with the same width, I sorted them by height in descending order. This ensures that when we consider heights, we don’t pick two envelopes with the same width (since one cannot fit into another of equal width).

LIS Optimization: After sorting, the problem reduces to finding the Longest Increasing Subsequence (LIS) of the heights.

Complexity: I used an O(N log N) approach with binary search (std::lower_bound) to find the LIS, instead of the O(N²) DP approach, which was necessary given the constraints.

Graph Construction: I treated this as a Topological Sort problem. Each element in the vectors is a node. For a vector like [1, 2, 3, 4], I added directed edges: 1 -> 2, 2 -> 3, and 3 -> 4.

Kahn’s Algorithm: 1. Calculated the in-degree of every unique number.
2. Added all nodes with in-degree 0 to a std::priority_queue (to maintain a consistent or sorted output if requested, like the 1 2 3 4 5 7 9 example).
3. Repeatedly popped the smallest element, added it to the result, and reduced the in-degree of its neighbours.

Complexity: O(V+E), where V is the number of unique elements and E is the total number of adjacent pairs in the input vectors.