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){
                    result.add(j);
                }
            }
            return result;
            
        }

  • 5
    I

    This girl is a genius


  • 0
    Y

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

    Negate

    very nice solution, clear enough


  • 3
    M

    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
    J
    This post is deleted!

  • 0
    K

    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
    X

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


  • 1
    U

    great solution


  • 0
    A
    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
    M

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


  • 0
    2

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


  • 0
    V

    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.