Why none of the questions has numerical constraints what are we supposed to assume ?


  • 0
    C

    I mean do we always assume limits fall within the int range ? Or we always take unsigned long long here ?


  • 0
    L

    Agreed. Very few problems in LeetCode specify the numerical constraints, usually, any number within the int range can appear. This is just okay, but I am not very comfortable with the fact that very very few problems specify the input size also. You can only "feel" how large the input is (1) by your intuition, (2) through the test case you TLEed. Specifically, for (2), if you are lucky, you can just read the "n" from the first line, and if you are not, you have to search how many commas there are in the given array to know the input size. This seems unfriendly, and I don't think knowing the input size precisely is a bad thing.

    At the end, I will give an example that I personally don't like the most in LeetCode in terms of the input size.
    Best Time to Buy and Sell Stock IV

    Clearly, one can first come up with an O(n^2 * k) DP solution, and then optimize it to an O(nk) one. The good part for LeetCode is that it has a test case for k = MAX_INT, which simply leads to an O(min(nk, n^2)) algorithm. But the bad part is that all the extreme test cases only focus on the following two aspects:

    1. Very large n and a small k,
    2. Very large n and very large k, where k >= n / 2.

    The time limit is set to let the O(min(nk, n^2)) solution fail for the second case. This somehow forces one to break his/her solution into two branches, i.e., use the above method to solve case 1, and use the O(n) solution of Stock ii to hack case 2.

    Most of the existing solutions posted online are all on this track, but I personally think this trick is ugly, and it is unnecessary to design the test cases in such a way to gruffly combine two problems. For instance, when k is sufficiently large, but k < n / 2, we cannot apply the O(n) solution, and the O(nk) one turns out to be slow as well. This case can simply crash many existing solutions, though it is not included in the OJ.

    I am no offensive to this problem or the existing solutions. I just want to use it as an example to show the importance of being specific to the input size. Let me know if you disagree with me, or you have any other ideas.


Log in to reply
 

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