Why this TLE?


  • 0
    C
    public class Solution {
        public List<Integer> findDisappearedNumbers(int[] nums) {
            List<Integer> ret = new ArrayList<>();
            for(int i = 0; i < nums.length; i++) {
                ret.add(i+1);
            }
            for(int i = 0; i < nums.length; i++) {
                if(ret.contains(nums[i])) ret.remove(ret.indexOf(nums[i]));
            }
            return ret;
        }
    }
    

    literally, it is O(n), and no extra space. Am I right?


  • 0
    I

    @chuR

    ret.contains(nums[i])
    

    is another iteration so this would be O(n2).


Log in to reply
 

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