contain duplicate

Question

How should I optimize this code sample,getting. Tlc
import java.util.*;
class Solution {
public boolean containsDuplicate(int[] nums) {
//tlc
int s =0;
boolean ans=true;
int e = nums.length-1;
if (nums.length <= 0) {
return false;
}
while(s<e){
if(nums[s]!=nums[e]){
ans =false;
s++;
e--;
}

}
return ans;

}
}

Answer 1

Yes i got what are you saying... thanks 👍

Answer 2

Mustafa A, vikram Rathod here is a way to reduce the number of comparisons to nlog(n). Only compare from i to the end of the list. The items before i have been compared already.

int end = nums.length;
for (int i = 0; i < end-1; i++) {
for (int j = i+1; j < end; j++) {
if (nums[i] == nums[j]) {
return true; // end here
}
}
}

return false; // no duplicates

Answer 3

First of all. A method that doesn't use object attributes should be static. You don't want to be forced to create an instance to use it.

If you find a duplicate, you don't want to continue. You should return immediately.

Otherwise, I would improve the readability of the code.

Like this:

int end = nums.length;
for (int i = 0; i < end; i++) {
for (int j = 0; j < end; j++)
{
if (i != j) { // ignore same element
if (nums[i] == nums[j]) {
return true; // end here
}
}
}
}

return false; // no duplicates

Answer 4

I think this could use the n^2 time complexity

Answer 5

Yeah. But time time complexity is about worst case. This could take anything from 2 (the first two are duplicates) to n^2 (last two are duplicates).

You don't need to force it. If there is one duplicate, then the list contains duplicates.

Answer 6

But its still showing TLC

Answer 7

vikram Rathod Try starting j with 1 instead. Otherwise it will compare the first element with itself for no reason.

Answer 8

vikram Rathod if you need further reduction in complexity, consider using a hashMap. That would reduce it to 2n -- that is, 1n to test for the number being already in the map with the containsKey() method, and subsequently 1n to add it to the map with the put() method.

Answer 9

Brian Yeah. That's true. Good point.