My accepted Java solution. Is it O(n^2) or O(n^3)?


  • 0
    S

    Hi, below is my solution. Is it O(n^2) or O(n^3)?

    public class Solution {
        public int threeSumSmaller(int[] nums, int target) {
            int ret = 0;
            Arrays.sort(nums);
            if(nums==null || nums.length<3) return ret;
            for(int i=0;i<nums.length;i++){
                for(int j=i+1;j<nums.length;j++){
                    int left = j+1;
                    while(left<nums.length){
                        if(nums[i]+nums[j]+nums[left]<target){
                            ret++;
                            left++;
                        }else break;
                    }
                }
            }
            return ret;
        }
    }

  • 0
    J

    Unfortunately, this is O(n^3). In extreme case where any three sum in the array is less than target, your code is exactly the same as three for loops.


  • 0
    J

    Unfortunately, this is O(n^3). In extreme case where any three sum in the array is less than target, your code is exactly the same as three for loops.

    https://leetcode.com/discuss/55410/ac-o-n-2-java-solution

    Check this one, this is a real O(n^2) solution.


Log in to reply
 

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