Sorted Containers Pattern

The pattern

A lot of “design a data structure” problems boil down to the same requirement: you need to insert data quickly, but you also need to query it by order — the nearest key to some value, or everything in a range. A plain Dictionary/hashmap gives you O(1) lookup by exact key, but it has no idea what “nearest” or “between” means. A plain list gives you order, but inserting into the middle is O(n).

The fix is a container that keeps its keys sorted as you insert — SortedDictionary or SortedList in C#, TreeMap in Java, the third-party sortedcontainers package in Python. Once the keys are sorted, range and nearest-neighbor questions turn into binary search, which is where the real complexity payoff comes from.

I ran into this pattern twice in a row while working through my LeetCodePatterns repo, so it earned its own post. Two problems, two different tools from the same drawer.

Design Log Storage System (LC 635)

The problem: logs come in as (id, timestamp) pairs, where the timestamp is a fixed-width, zero-padded string like "2017:01:01:23:59:59". You need to store them, then retrieve every id whose timestamp falls in [start, end] — but “falls in range” is defined at a given granularity. If granularity is "Day", then "2017:01:01:23:59:59" and "2017:01:01:00:00:01" are the same bucket, because everything past the day field gets ignored for the comparison.

Here’s the actual implementation:

public class LogStorageSystem
{
    private SortedDictionary<int, string> logs = new SortedDictionary<int, string>();

    public void Put(int id, string timestamp)
    {
        logs[id] = timestamp;
    }

    public IList<int> Retrieve(string start, string end, string granularity)
    {
        string NormalizeTimestamp(string timestamp, bool isEnd)
        {
            return granularity switch
            {
                "Year"
                    => timestamp.Substring(0, 4) + (isEnd ? ":12:31:23:59:59" : ":01:01:00:00:00"),
                "Month" => timestamp.Substring(0, 7) + (isEnd ? ":31:23:59:59" : ":01:00:00:00"),
                "Day" => timestamp.Substring(0, 10) + (isEnd ? ":23:59:59" : ":00:00:00"),
                "Hour" => timestamp.Substring(0, 13) + (isEnd ? ":00:00" : ":00:00"),
                "Minute" => timestamp.Substring(0, 16) + (isEnd ? ":00" : ":00"),
                "Second" => timestamp,
                _ => throw new ArgumentException("Invalid granularity"),
            };
        }

        string startKey = NormalizeTimestamp(start, false);
        string endKey = NormalizeTimestamp(end, true);

        List<int> result = new List<int>();

        foreach (var log in logs)
        {
            if (string.Compare(log.Value, startKey) >= 0 && string.Compare(log.Value, endKey) <= 0)
            {
                result.Add(log.Key);
            }
        }

        return result;
    }
}

The trick that makes this work is normalization, not the sorted container itself. Since the timestamp format is fixed-width and every field is zero-padded, lexicographic string comparison and chronological comparison agree completely — "2017:02:01..." > "2017:01:31..." as strings, exactly like it is in time. That means once you round start down to the floor of its granularity bucket and round end up to the ceiling of its bucket, a plain string.Compare does all the range-membership work for you. "Day" granularity turns start into midnight of that day and end into 23:59:59 of that day — anything with the same date prefix now compares as being inside the window.

Where the SortedDictionary actually earns its keep here is Put — O(log n) insert keeping ids ordered — but honestly Retrieve doesn’t take advantage of the sort at all. It does a full O(n) linear scan over every stored log and string-compares each one against the normalized bounds. A sharper version would binary-search into the sorted structure for the start boundary and walk forward only through the matching range, dropping retrieve down to O(log n + k) where k is the result size. That’s not a bug — the code is correct — just an optimization left on the table, which is a common thing to notice once you’ve internalized the pattern: having a sorted container doesn’t automatically mean your code is using the ordering.

Time Based Key-Value Store (LC 981)

The problem: implement set(key, value, timestamp) and get(key, timestamp), where set timestamps are strictly increasing per key, and get should return the value stored at the largest timestamp that is <= the query timestamp (or "" if none exists). This is the classic floor/predecessor query.

public class TimeMap
{
    private readonly Dictionary<string, SortedList<int, string>> data;

    public TimeMap()
    {
        data = new Dictionary<string, SortedList<int, string>>();
    }

    public void Set(string key, string value, int timestamp)
    {
        if (!data.TryGetValue(key, out var list))
        {
            list = new SortedList<int, string>();
            data[key] = list;
        }
        list.Add(timestamp, value);
    }

    public string Get(string key, int timestamp)
    {
        if (!data.TryGetValue(key, out var keys)) return "";

        var left = 0;
        var right = keys.Keys.Count - 1;
        var ans = -1;
        while (left <= right)
        {
            var mid = left + (right - left) / 2;
            if (keys.Keys[mid] == timestamp) return keys.Values[mid];
            if (keys.Keys[mid] <= timestamp)
            {
                ans = mid;
                left = mid + 1;
            }

            else
            {
                right = mid - 1;
            }
        }

        if (ans != -1) return keys.Values[ans];

        return "";
    }
}

Here the design is a Dictionary<string, SortedList<int, string>> — a hashmap for the O(1) key lookup, and a per-key SortedList to keep that key’s timestamps ordered as they arrive. Since Set is documented to receive strictly increasing timestamps, every insert lands at the tail, so list.Add is effectively O(log n) amortized (SortedList keeps its backing array sorted, so worst case an insert can shift elements, but for a monotonic append pattern it’s cheap in practice).

Get is a manual binary search over keys.Keys — no built-in “find predecessor” method on SortedList, so it’s hand-rolled. The trick worth internalizing: instead of narrowing until left == right and then checking, it tracks ans — the best candidate found so far — every time keys.Keys[mid] <= timestamp is true. That candidate might still get beaten by a larger valid timestamp further right, so the search keeps going (left = mid + 1) instead of stopping. If keys.Keys[mid] overshoots, it discards the right half (right = mid - 1). By the time left > right, ans holds the index of the largest timestamp not exceeding the query — the classic “track the answer, don’t stop at first match” shape you’ll see in every floor/ceiling binary search. Both Set and Get are O(log n).

Try it: watching the floor search

Below is that exact Get binary search, running against timestamps [1, 4, 7, 9, 15, 20] for key = "k", querying get("k", 12). The expected answer is 9 — the largest stored timestamp that doesn’t exceed 12. Step through it and watch left/right close in while ans gets updated only when a candidate actually survives.

Blue = current mid. Dimmed = eliminated range. Green outline = current best candidate for the answer; solid green = the final floor value.

Takeaways

Both problems reach for a sorted container, but for different reasons. SortedDictionary in the log system buys ordered iteration and O(log n) insert, though the retrieve path in this implementation doesn’t actually exploit the ordering — it’s a reminder that “I used a sorted structure” and “I got the sorted-structure speedup” aren’t automatically the same claim. SortedList plus a hand-rolled binary search in the time map is the more classic use of the pattern: keep keys ordered so you can binary-search for a floor/predecessor in O(log n) instead of scanning. The ans-tracking binary search — keep searching after a hit instead of stopping — is the one piece of this I’ll reuse the most; it’s the same shape as finding the last occurrence, the insertion point, or any other “closest qualifying value” search.