For the time complexity, I understand O(n) is from each "check()" on the entire nums array. Does M == (Integer.MAX_VALUE - Integer.MIN_VALUE) ? so it will be O(n log ( Integer.MAX_VALUE - Integer.MIN_VALUE)).
I think people mentioned in the earlier post that since the array element domain is between -10000 and 10000. We can tighten the time complexity to O(n log ( 20000) ), which can be approximated to O(n)