# Untitled

user_4319476
plain_text
15 days ago
3.8 kB
1
Indexable
Never
```To solve this follow-up, we can modify our space-efficient solution to support range queries efficiently. Here's how we can approach this:

Keep the existing structure (fixed-size array) for space efficiency.
Use binary search to find the start and end points of the range.
Implement the range query method.

Here's the modified implementation:
javaCopyclass TimeMap {
private static final int N = 5; // Number of recent values to keep per key
private Map<String, TimestampedValue[]> map;

private static class TimestampedValue {
int timestamp;
String value;

TimestampedValue(int timestamp, String value) {
this.timestamp = timestamp;
this.value = value;
}
}

public TimeMap() {
map = new HashMap<>();
}

// Existing set and get methods remain the same

public List<String> getRange(String key, int startTime, int endTime) {
List<String> result = new ArrayList<>();
TimestampedValue[] values = map.get(key);
if (values == null) return result;

int startIndex = findLowerBound(values, startTime);
int endIndex = findUpperBound(values, endTime);

for (int i = startIndex; i <= endIndex; i++) {
if (values[i] != null && values[i].timestamp >= startTime && values[i].timestamp <= endTime) {
}
}

return result;
}

private int findLowerBound(TimestampedValue[] values, int timestamp) {
int left = 0, right = N - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (values[mid] == null || values[mid].timestamp < timestamp) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return left;
}

private int findUpperBound(TimestampedValue[] values, int timestamp) {
int left = 0, right = N - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (values[mid] == null || values[mid].timestamp <= timestamp) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return right;
}

// Existing helper methods (findInsertionIndex, findFloorIndex) remain the same
}
Key points of this solution:

Space Efficiency:

Maintains the fixed-size array (N = 5) for each key, preserving space efficiency.

Time Complexity:

getRange(): O(log N + K), where N is the size of the array (5 in this case) and K is the number of entries within the range.
Binary search is used to find the start and end points: O(log N)
Iterating through the range to collect results: O(K)

Range Query Implementation:

findLowerBound: Finds the index of the first element greater than or equal to startTime.
findUpperBound: Finds the index of the last element less than or equal to endTime.
Iterate through the range to collect values within the specified time range.

Maintaining Existing Operations:

The set() and get() methods remain unchanged, preserving their original time and space complexities.