Clean and efficient C++ solution 🐈‍⬛🐈‍⬛
IntuitionAs I see this problem's test case size(105), I first come up with the idea about binary search. It's lucky that it's work. Or maybe I'll think about dy
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
As I see this problem's test case size($$10^5$$), I first come up with the idea about binary search. It's lucky that it's work. Or maybe I'll think about dynamic programming since it need to find the minimum value.

# Approach
<!-- Describe your approach to solving the problem. -->
This is a binary search on values, not indices. There are two types of binary search:

1. Searching within an array (e.g., finding a target value in a sorted list).
2. Searching for a value by checking its feasibility.

This problem is the second type.

To solve the problem by binary search.We need to go with two step:
## 1. Determine the search range:
The minimum possible answer is the smallest value in the array, and the maximum is the largest value. Searching beyond this range is unnecessary. Alternatively, we can use the problem's constraints (1≤nums[i]≤$$10^9$$), but this may lead to more iterations.

## 2. Check if a given value is feasible:
We use a greedy approach: iterate through the array and select elements while ensuring that:
- The selected value is below the current threshold.
- It does not violate the "no adjacent selection" rule.

If we can pick at least k elements, the value is feasible.

### Why does this greedy approach work?
Suppose the current threshold is mid= 10 and the array starts with [3,4,…]. If both 3 and 4 are valid choices, should we always pick the first one?

1. If the third element is greater than mid (e.g.,[3,4,11]), then picking 4 instead of 3 reduces the answer length to 1, whereas choosing 3 allows us to pick another element later.

2. If the third element is also valid (e.g., [3,4,5]), we check the fourth element:
If the fourth element is also valid (e.g., [3,4,5,6]), then either 3 or 4 as the first choice works.
However, if the fourth element is greater than mid (e.g.,[3,4,5,11]), then picking 4 limits the sequence length to 1 (nums[1]), while picking 3 allows us to form a longer sequence (nums[0], nums[2]).
This shows that following the greedy approach always maximizes the sequence length.

that is if we follow the greedy approach we can get the answer maximize the answer length.

# Complexity
- Time complexity:$$O(nlong)$$
<!-- Add your time complexity here, e.g. $$O(n)$$ -->
Since we need to do $$O(logn)$$ iteration and check if it feasible in $$O(n)$$ time.the Time complexity is $$O(n)$$*$$O(logn)$$=$$O(nlogn)$$
- Space complexity:$$O(1)$$
<!-- Add your space complexity here, e.g. $$O(n)$$ -->
since we only need to set left bound and right bound for binary search and their is no recursion function call in our algorithm. The Space complexity=$$O(1)$$

![45337FA9-ECF2-426D-8192-96239E10BE12-4.jpg](https://assets.leetcode.com/users/images/62a359a4-d109-4de9-9d08-ce3b0eacef56_1742064409.156774.jpeg)


# Code
```cpp []
class Solution {
public:
    bool stolable(vector<int>& nums,int k , int mid){
        int cnt=0;
        int prev=-2;//make sure we can take index 0 element if it value is smaller than mid.
        for(int i =0;i<nums.size();i++){
            if((i-prev)>=2&&nums[i]<=mid){
                prev=i;
                cnt+=1;
            }
        }
        return cnt>=k;
    }
    int minCapability(vector<int>& nums, int k) {
        int l = INT_MAX;
        int r = 0;
        for(int i:nums){
            l=min(l,i);
            r=max(r,i);
        }
        while(l<r){
            int mid=l+(r-l)/2;
            if(stolable(nums,k,mid))r=mid;
            else l=mid+1;
        }
        return l;
    }
};
```
['C++']