Arrays - chapter5

In-Place Operations

These are very important from an interviewing standpoint.

In-place Array operations are where we modify an Array, without creating a new Array.

:  inserting and removing items by shifting existing items along.

In programming interviews, the interviewer often expects you to minimise the time and space complexity of your implementation. In-place Array operations help to reduce space complexity, and so are a class of techniques that pretty much everybody encounters regularly in interviews.

 

***In-place Array operations are a big deal for programming interviews, where there is a big focus on minimising both time and space complexity of algorithms.

public int[] squareEven(int[] array, int length) {

  // Check for edge cases.
  if (array == null) {
    return array;
  }

  // Iterate through the original array.
  for(int i = 0; i < length; i++) {

    // If the index is an even number, then we need to square the element
    // and replace the original value in the Array.
    if (i % 2 == 0) {
      array[i] *= array[i];
    }
    // Notice how we don't need to do *anything* for the odd indexes? :-)
  }

  // We just return the original array. Some problems on leetcode require you
  // to return it, and other's dont.
  return array;
}

 

 

An important difference for in-place vs not in-place is that in-place modifies the input Array. This means that other functions can no longer access the original data, because it has been overwritten. We'll talk more about this in a bit.

 

Replace Elements with Greatest Element on Right Side (memory usage 21.66% 432ms)

class Solution {
    public int[] replaceElements(int[] arr) {
        int len = arr.length;
        
        for(int i = 0; i<len-1;i++){
            arr[i] = findMax(arr, i+1, len);
        }
        arr[len-1] = -1;
        return arr;
    }
    
    private int findMax(int[] arr, int start, int len){
        int max = 0;
        for(int i = start; i<len;i++){
            max = Math.max(arr[i], max);
        }
        return max;
    }
}

 

더 나은 방법 생각하기( 2ms - 50.21%, 36.40%)

class Solution {
    public int[] replaceElements(int[] arr) {
        int max= -1;
        for(int i = arr.length-1;i>=0;i--){
            if(max<arr[i]) {
                int temp = arr[i];
                arr[i] = max;
                max = temp;
            }else {
                arr[i] = max;
            }    
        }
        return arr;
    }
}

 

A Better Repeated Deletion Algorithm - Intro 

Example)

public int[] copyWithRemovedDuplicates(int[] nums) {
        
  // Check for edge cases.
  if (nums == null || nums.length == 0) {
      return nums;
  }

  // Count how many unique elements are in the Array.
  int uniqueNumbers = 0;
  for (int i = 0; i < nums.length; i++) {
      // An element should be counted as unique if it's the first
      // element in the Array, or is different to the one before it.
      if (i == 0 || nums[i] != nums[i - 1]) {
          uniqueNumbers++;
      }
  }

  // Create a result Array.
  int[] result = new int[uniqueNumbers];

  // Write the unique elements into the result Array.
  int positionInResult = 0;
  for (int i = 0; i < nums.length; i++) {
    // Same condition as in the previous loop. Except this time, we can write
    // each unique number into the result Array instead of just counting them.
      if (i == 0 || nums[i] != nums[i - 1]) {
          result[positionInResult] = nums[i];
          positionInResult++;
      }
  }
  return result;
}

  Remove Duplicates from Sorted Array

앞에서 풀었던 문제를 memory를 적게 쓸 뿐만 아니라, 시간도 적게 하는 방법을 찾아보게끔 한 번 더 출제한 듯하다.

혼자 힘으로 다시 푸어보았다. (33.18%, 13.87%)

class Solution {
    public int removeDuplicates(int[] nums) {
        int change = 0;
        
        for(int i = 1; i<nums.length;i++){
            if(nums[i] == nums[change])continue;
            if(nums[i]>nums[change]){
                nums[change+1] = nums[i];
                change++;
            }      
        }
        return change+1;
    }
}

 

A Better Repeated Deletion Algorithm - Answer

 

:This was just a very brief introduction to the very versatile and widely used two-pointer technique. It is one of the main techniques used for in-place Array algorithms.

public int removeDuplicates(int[] nums) {
        
  // Check for edge cases.
  if (nums == null) {
      return 0;
  }
  
  // Use the two pointer technique to remove the duplicates in-place.
  // The first element shouldn't be touched; it's already in its correct place.
  int writePointer = 1;
  // Go through each element in the Array.
  for (int readPointer = 1; readPointer < nums.length; readPointer++) {
      // If the current element we're reading is *different* to the previous
      // element...
      if (nums[readPointer] != nums[readPointer - 1]) {
          // Copy it into the next position at the front, tracked by writePointer.
          nums[writePointer] = nums[readPointer];
          // And we need to now increment writePointer, because the next element
          // should be written one space over.
          writePointer++;
      }
  }
  
  // This turns out to be the correct length value.
  return writePointer;
}

 

It's important to know when to use in-place Array operations—they might not always be the way to go.

For example, if we'll need the original array values again later, then we shouldn't be overwriting them. In these cases, it's best to create a copy to work with, or to simply not use in-place techniques. It's important to be very careful when working with existing code that somebody else has written. If other code is depending on the original Array to work, then you might completely break the program if you modify that Array!

 

 

Move Zeroes (28.94%, 14.63%)

class Solution {
    public void moveZeroes(int[] nums) {
        //새로운 배열 만들지 않고 해야 함
        int len = nums.length;
        int i =0; int j = 0;
        while(i<len){
            if(nums[i] != 0) {
                //변경 필요
                int temp = nums[i];
                nums[i] = nums[j];
                nums[j] = temp;
                i++;
                j++;
            }else {
                i++;
            }
        }
    }
}

 

public void moveZeroes(int[] nums) {
        int index = 0;
        
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != 0) {
                nums[index++] = nums[i];
            }
        }
        
        for (int i = index; i < nums.length; i++) {
            nums[i] = 0;
        }
        
    }

Sort Array By Parity

위의 문제와 원리는 동일하다. (32.79%, 21.43%)

class Solution {
    public int[] sortArrayByParity(int[] nums) {
        int index = 0; 
        int change = 0;
        int len = nums.length;
        while(index<len){
            if(nums[index]%2 == 0){
                int temp = nums[index];
                nums[index++] = nums[change];
                nums[change++] = temp;
            }else {
                index++;
            }
        }
       return nums; 
    }
}

 

Remove Element

마지막 문제도 위의 것과 동일하게 구할 수 있다! (0ms, 80.99%)

class Solution {
    public int removeElement(int[] nums, int val) {
        int k = 0;
        int change= 0;
        
        for(int i = 0;i<nums.length;i++){
            if(nums[i] != val){
                int temp = nums[i];
                nums[i] = nums[k];
                nums[k] = temp;
                k++;
            }
        }
     return k;   
    }
}