# 2ms O(n) In-Space Java

• Think we surely have to negate anytime we are given an array with values from 1 to the length of array. If anyone has a better idea, will be happy to hear.

The steps followed in this is:

1. Negate each number while traversing
2. Run again and find the index that is not negated.
``````        List<Integer> result = new ArrayList<Integer>();
for( int i=0;i< nums.length; i++){
int index = nums[i];
if(nums[Math.abs(index)-1] > 0){
nums[Math.abs(index)-1]= -nums[Math.abs(index)-1];
}
}

for(int j =1 ;j <= nums.length ; j++){
if(nums[j-1] > 0){
}
}
return result;

}``````

• This girl is a genius

• said in 2ms O(n) In-Space Java:

Negate

very nice solution, clear enough

• Awesome solution. Much better than my own. Good work. :)

I thought of a small suggestion for improvement:
Since you are assigning index, consider assigning it as follows:

``````int index = Math.abs(nums[i])-1;
``````

I don't know Java well, but I think this will save you 2 extra calls to the Math.abs(...) function and all the associated overhead.

• This post is deleted!

• the solution is great, but I got 20ms with these code, far away from 2ms, what's wrong?

• @Kuuuuuuuo I think they might have added more Test cases cause of which it has increased to 20ms.

• @Kuuuuuuuo I got 193ms with the same code in C++...

• great solution

• This post is deleted!

• I adopted @mclachlan 's suggestion and it did speed up the algorithm a little bit so as to be comparable with the not-in-place version.

Despite the running time, this is a clever algorithm to satisfy the space requirement. Nicely done and tks for sharing.

• @gayathri3 hey, can you explain what the purpose of Math.abs(index) - 1 is?

• @mrBrightside step through the code with debugger and/or pen/paper to see the reasoning behind it

• Nice solution.

The code can take some optimizng:

``````int index = Math.abs(index) - 1;
``````for (int i = 0; i < nums.length; i++) {