[Contest][1]

[Practice][2]

**Author:** [Shivam Garg][3]

**Tester:** [Shiv Dhingra][4]

### DIFFICULTY

EASY

### PREREQUISITES

Basic Knowledge of Sets (STL)

### PROBLEM

Given a list of integers, for each of them **find the maximum number less than the given number preceding it**.

### EXPLANATION

The brute approach will turn out to be of complexity O(N ^2), and hence is bound to time out.

We can maintain a **sorted set** of numbers by iterating over the array. In other words, if we have a set of numbers preceding the given number, we can easily find out the largest number smaller than the given number.

We can simply perform **binary search** in this set to find the number just less than the given number.

This can be done by using **lower_bound** command of the set in C++, or equivalent in other languages.

```
set<long long>::iterator it = s.lower_bound(val);
it--;
return (*it);
```

This will fulfill our task. The complexity of accessing/inserting elements in the set is O(Log(N)).

So, the overall complexity turns out to be O(N \hspace{1 mm} Log(N)).

### SOLUTION

Setterâ€™s Solution -

```
[5]
[1]: https://www.codechef.com/CODR2018/problems/KRYP6
[2]: https://www.codechef.com/problems/KRYP6
[3]: http://codechef.com/users/shivamg_isc
[4]: http://codechef.com/users/lucifer2709
[5]: https://www.codechef.com/viewsolution/17468627
```