Some thoughts about many Java solutions


  • 0
    G

    The input given is List<List<Integer>> triangle.
    I think it is problematic to assume those 'List's having O(1) time for get(i) or set(i).
    For example, triangle.get(i), could take O(n) time, if the list is of LinkedList. Only exception is that you get or set at the first or last element of a list, where you do have O(1).
    There are a couple of sample solutions using 'triangle.get(i).get(j)' and got accepted luckily. So I guess OJ does use ArrayLists for testing purpose because ArrayList does have O(1) for get/set. Had the OJ used LinkedList for inputs, 'triangle.get(i)(j)' would use O(n^2) to just get the element.


  • 0
    L

    If "n" is the number of the rows in the input matrix, then the complexity of traverse all elements is O(n^2). But if "n" is the number of elements in the matrix, then I think the complexity of an algorithm that traverses all elements should be O(n).


Log in to reply
 

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