Skip to content

Latest commit

 

History

History
17 lines (10 loc) · 1012 Bytes

File metadata and controls

17 lines (10 loc) · 1012 Bytes

Offline Query

A common trick for solving problems related to a series of queries.

When we know all the queries upfront, we can sort the query and the original data in some order so that we can scan the query and the original data simultaneously (which takes O(N + Q) time), instead of scanning all original data for each query (which takes O(N * Q) time).

The name "offline" signifies the fact that we know all the queries upfront/offline. If the queries keep streaming in (i.e. online), we can't reorder the queries to get a better time complexity.

Problems

Discuss

https://leetcode.com/problems/most-beautiful-item-for-each-query/discuss/1576065/C%2B%2B-Offline-Query