CODEWITHSUNDEEP
c++algorithmdictionarydata-structuresstl
rsaha77
rsaha77

Reputation: 163

Finding key corresponding to max value in c++ map

Given a number say 'KEY' and map <int, int> myMap. I am trying to find a smallest key k (condition: k < KEY) in the map myMap such that it's value is maximum.

Example:

map <int, int> myMap = {{3,1}, {4,3}, {5,2}, {6,3}, {7,2}, {8,5}};
                             // ^^^
int KEY = 7;

Answer is 4, since for all the keys less than 7(KEY), the key 4 and key 6 has the maximum value of 3. 4 is the smallest key.

The map increases dynamically and there are several such queries with KEY.

I am trying to get the {k,v} pair in O(logN) time

I'm stuck after using lower_bound. Using lower bound gives me max 'k' such that k < KEY. In the example above I am able to get {7,2} for KEY=7. But struggling to get to {4,3} in logN time. Is there any data structure which can help me achieve this in logN time?

Update:

I am making sure to do the updates to the map in logarithmic time as well. Integers are not exceeding 10^5. Is it possible to use some other data structure and approach (in this case it looks like dynamic programming/binary search) to solve this in logarithmic time?

Upvotes: 1

Views: 1189

Answers (2)

Igor Tandetnik
Igor Tandetnik

Reputation: 52471

How about this. You maintain a secondary map, a subset of your primary one. Specifically, this secondary map would contain {k, v} if and only if all smaller keys in the primary map correspond to smaller values.

For your example of {3,1}, {4,3}, {5,2}, {6,3}, {7,2}, {8,5}, this secondary map would be {3,1}, {4,3}, {8,5}. Observe how values are monotonously increasing along with keys.

It should be obvious how to use this map to answer the question - simply look up the key with lower_bound. In the example, for the key of 7, the lookup will find 4, the correct answer.

Now, how to maintain this map. When you insert {k, v} into the primary map, look up k in the secondary map using lower_bound. There are two possibilities:

  • There exists a smaller key with equal or larger value. Do nothing, the secondary map doesn't need to be updated.

  • There doesn't exist a smaller key, or the smaller key corresponds to a smaller value. Then

    • Insert {k, v} into the secondary map
    • Walk keys sequentially, starting from k until you encounter the key k' with a larger value, or reach the end. Erase the range between k and k' (exclusive of both), or from k (exclusive) to the end.

On the surface, this last step looks linear - but in fact it's amortized constant. Over N insertions, this step would have to walk 2*N elements at most (e.g. first N-1 steps inserting one element each, and the last step removing them all and inserting one).

Upvotes: 1

Captain Giraffe
Captain Giraffe

Reputation: 14705

Is there any data structure which can help me achieve this in logN time?

Not really unless you are able to combine those values in a meaningful fashion. All (almost) log N algorithms relies on a divide and conquer approach.

You have essentially two unrelated sequences. The key mapped by tree allows you to do log N stuff but then you need another search on an unstructured sequence this is O(N).

So for this to be done on O(log N) you need to somehow combine the key and the value or go the route comment @Igor suggested which is essentially a map of maps.

Of course tweaking implementation might bring benefits but not O(N) -> O(log N) type benefits.

Upvotes: 0

Related Questions