This problem O(n^2) is ok?


  • 4
    Y

    O(n^2) I got Time Limit Exceed. Does anyone got accept by O(n^2) ? I just use binary search and finally accept.


  • 0
    S

    Nope, O(N^2) is a brute force solution. As I know, the best time complexity of it is O(N log N).


  • 24
    F

    You may use HashTable and solve the problem in O(N) time / O(N) space complexity

    import java.util.Hashtable; //import hashtable utility
    public class Solution {
        public int[] twoSum(int[] numbers, int target)
        {
            int []a = new int[2];
    		Hashtable<Integer, Integer> nums = new Hashtable<Integer, Integer>();
    		for (int i=0; i<numbers.length; i++)
    		{
                //put number into hash table (if it's not already there)
    			Integer n = nums.get(numbers[i]);
    			if (n==null) nums.put(numbers[i], i); //subtract array element from target number
    			n = nums.get(target-numbers[i]); 
    			if (n!=null && n<i)
    			{//if such number exists in the table return the indicies
    				a[0]=n+1;
    				a[1]=i+1;
    				return a;
    			}
    		}
         return a;
        }
    }

  • 0
    G

    This following O(n^2) solution was accpeted by the judge.

    class Solution {
    public:
        vector<int> twoSum(vector<int> &numbers, int target) {
            
            int i,j;
            vector<int> v;
            for(i=0;i<numbers.size();i++)
                for(j=i+1;j<numbers.size();j++)
                    if(numbers[i]+numbers[j]==target)
                    {
                        v.push_back(i+1);
                        v.push_back(j+1);
                        return v;
                    }
        }
    };
    

    EDIT : The first time, I submitted this code it got accepted in 40ms but the same code now gives a TLE.


  • 0
    S

    no, still got TL with O(n^2)


  • 0
    G

    Did you run my code and get a TL?


  • 0
    S

    yes.. i think they add some hard tests... however, the same algorithm O(n2) gets accepted in JAVA, i've no idea why..


  • 0
    G

    Try resubmitting you code and see if it still gets accepted.


  • 0
    G

    I think it's a good idea to use hash, but what if the elements are not unique? say, {2, 3, 3, 4}, target = 6


  • 0
    S

    O(n2) C++ code always gets TL (i have tried mine and yours)


  • 0
    G

    No, I meant to ask whether you tried resubmitting your O(n^2) Java code and if the resubmission passed or got a TLE?


  • 0
    S

    O(n^2) java code gets accepted... that is strange!


  • 0
    F

    Given the assumption "each input would have exactly one solution" the above implementation should work with duplicates as well. In the example above, when first 3 is encountered, the loop would check if target-numbers[i] (6-3=3) exists in hash table. It does not, thus 3 is put into the hash table. When second 3 is encountered the loop again checks (6-3). This time 3 exists in the hash, thus returns indices of 3 and 3 from numbers array.


  • 0
    G

    I was trying using the hash solution, and i found I got the result of the identical positions , say [2, 2], cuz as checking 'target - numbers[i]' it would get the 3 from where i just put in hash, 'nums.put(numbers[i], i)'. And I found mine didn't have the condition 'n < i'.
    Finally, my solution is check target - numbers[i] first, if found, then just return. Otherwise put the current value into hash table.


  • 0

    @dr Now O(N^2) Java solution should not get Accepted.


  • 6
    J
    import java.util.Hashtable; //import hashtable utility
    public class Solution {
        public int[] twoSum(int[] numbers, int target) {  
            // Start typing your Java solution below  
            // DO NOT write main() function  
            HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();  
            int n = numbers.length;  
            int[] result = new int[2];  
            for (int i = 0; i < numbers.length; i++)  
            {  
                if (map.containsKey(target - numbers[i]))  
                {  
                    result[0] = map.get(target-numbers[i]) + 1;  
                    result[1] = i + 1;  
                    break;  
                }  
                else  
                {  
                    map.put(numbers[i], i);  
                }  
            }  
            return result;  
              
        } 
    }

  • 0
    R

    it doesn't matter whether the judge accepts n^2 solution. because no interviewer in real world would..


  • 0
    Z

    I try to use O(n^2), and get TLE when n > 16000.
    Just use sort and binary search can get o(nlogn)


  • 0
    T

    This is not O(n) space. Suppose input size is O(n) and target=2^n, then space is O(2^n)


  • 0
    T

    This is not O(n) space. Suppose input size is O(n) and target=2^n, then space is O(2^n)


Log in to reply
 

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