# This problem O(n^2) is ok?

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

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

• 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;
}
}``````

• 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.

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

• Did you run my code and get a TL?

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

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

• 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

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

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

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

• 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.

• 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.

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

• ``````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;

}
}``````

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

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

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

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

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