2ms O(n) In-Space Java

  • 26

    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;

  • 5

    This girl is a genius

  • 0

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


    very nice solution, clear enough

  • 3

    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.

  • 0
    This post is deleted!

  • 0

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

  • 0

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

  • 0

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

  • 1

    great solution

  • 0
    This post is deleted!

  • 1

    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.

  • -1

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

  • 0

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

  • 0

    Nice solution.

    The code can take some optimizng:

    • assign index(@mclachlan 's suggestion):
      int index = Math.abs(index) - 1;
    • last for loop, index can start with 0, may reduce some subtraction operations:
      for (int i = 0; i < nums.length; i++) {
          if (nums[i] > 0) {
              results.add(i + 1);

Log in to reply

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