Correct me if I'm wrong but I expect this to throw an ArrayIndexOutOfBoundsException for array.length >= 2^16 (i.e. Integer.MAX_SIZE / 2). Better add a check for start < 0 as well. Unfortunately I don't think this is feasible for test cases (Integer.MAX_SIZE / 5 already blows up 4GB of heap..)

You are making extra calls to getHeight then required. Would increase your time of execution.
Holding the height infomration once caluculated might be a better solution.