# Share my C++ solution, O(lg(n)) to pick, O(nlg(n)) for sorting

• Pre-process sorting for O(nlg(n))
Pick in O(lg(n)) using binary search
O(n) space to store value/index pairs

``````class Solution {
public:
typedef pair<int, int> pp; // <value, index>

static bool comp(const pp& i, const pp& j) { return (i.first < j.first); }

vector<pp> mNums;

Solution(vector<int> nums) {
for(int i = 0; i < nums.size(); i++) {
mNums.push_back(pp({nums[i], i}));
}
sort(mNums.begin(), mNums.end(), comp);
}

int pick(int target) {
pair<vector<pp>::iterator, vector<pp>::iterator> bounds = equal_range(mNums.begin(), mNums.end(), pp({target,0}), comp);
int s = bounds.first - mNums.begin();
int e = bounds.second - mNums.begin();
int r = e - s;
return mNums[s + (rand() % r)].second;
}
};
``````

• Nice Solution! But can you give some brife explanation? I do the sort first, but I don't know where is your binary search? Please, just write some comment.

• @dader the binary search is done by equal_range()

• I get a cryptic compile error, can you check?

``````required from 'std::pair<_FIter, _FIter> std::__equal_range(_ForwardIt
erator, _ForwardIterator, const _Tp&, _CompareItTp, _CompareTpIt) [wit
h _ForwardIterator = __gnu_cxx::__normal_iterator<std::pair<int, int>*
, std::vector<std::pair<int, int> > >; _Tp = std::pair<int, int>; _Com
pareItTp = __gnu_cxx::__ops::_Iter_comp_val<bool (*)(std::pair<int, in
t>&, std::pair<int, int>&)>; _CompareTpIt = __gnu_cxx::__ops::_Val_com
p_iter<bool (*)(std::pair<int, int>&, std::pair<int, int>&)>]'
``````

• @StefanPochmann oops, I posted wrong one, the arguments of comp() should be const
I've fixed it in original post, thanks

``````    static bool comp(const pp& i, const pp& j) { return (i.first < j.first); }
``````

• @chin-heng Man, g++ is so smart when it comes to optimizing code for speed, but so dumb when it comes to optimizing error messages for readability. Why couldn't it just say "the arguments of comp() should be const" like you did :-)

• A Python version:

``````class Solution(object):

def __init__(self, nums):
self.sorted = sorted(zip(nums, range(len(nums))))

def pick(self, target):
start = bisect.bisect_left(self.sorted, (target,))
stop = bisect.bisect_left(self.sorted, (target + 1,))
return self.sorted[random.randrange(start, stop)][1]
``````

• @StefanPochmann absolutely...it took me some time decoding when I first got the error message...

• Nice solution! I think there may be opportunity for clean up, if I may suggest :-)

``````auto bounds = equal_range(...)

// The number of equal items is this:
auto N = distance(bounds.first, bounds.second);

// Could short-circuit if N == 1
if(N == 1)
return bounds.first->second;

// For return, can index off the bounds iterator:
return bounds.first[rand() % N].second;
``````

• @StefanPochmann
Tried submitting your Python version a few times, but I kept getting MLE on the 13th test case :(
Perhaps the limits have been adjusted

• Nice solution, although function pick can be simplified as:

``````int pick(int target) {
auto bounds = equal_range(mNums.begin(), mNums.end(), pp({target,0}), comp);
return (bounds.first+rand()%(bounds.second-bounds.first))->second;
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.