Array

Array type of questions were asked in interviews frequently. You will most likely encounter one during your interviews.

We recommend:

Single Number,
Rotate Array,
Intersection of Two Arrays II and
Two Sum

26. Remove Duplicates from Sorted Array

leetcode.com/problems/remove-duplicates-from-sorted-array/

Given a sorted array nums, remove the duplicates in-place such that each element appear only once and return the new length.

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

Example 1:

Given nums = [1,1,2], Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively. It doesn't matter what you leave beyond the returned length.

Example 2:

Given nums = [0,0,1,1,1,2,2,3,3,4], Your function should return length = 5, with the first five elements of nums being modified to 0, 1, 2, 3, and 4 respectively. It doesn't matter what values are set beyond the returned length.

Clarification:

Confused why the returned value is an integer but your answer is an array?

Note that the input array is passed in by reference, which means modification to the input array will be known to the caller as well.

Internally you can think of this:

// nums is passed in by reference. (i.e., without making a copy) int len = removeDuplicates(nums); // any modification to nums in your function would be known by the caller. // using the length returned by your function, it prints the first len elements. for (int i = 0; i < len; i++) { print(nums[i]); }

정렬 된 배열 번호가 주어지면 각 요소가 한 번만 나타나고 새 길이를 반환하도록 중복 항목을 제자리에서 제거합니다.

다른 배열에 추가 공간을 할당하지 마십시오. 입력 배열을 O (1) 추가 메모리로 제자리에 수정하여이를 수행해야합니다.

예 1 :

주어진 nums = [1,1,2],

함수는 length = 2를 반환해야하며 nums의 처음 두 요소는 각각 1과 2입니다.

반환 된 길이를 초과하여 남겨 두는 것은 중요하지 않습니다.
예 2 :

주어진 숫자 = [0,0,1,1,1,2,2,3,3,4],

함수는 length = 5를 반환해야하며 nums의 처음 5 개 요소는 각각 0, 1, 2, 3 및 4로 수정됩니다.

반환 된 길이를 초과하여 설정되는 값은 중요하지 않습니다.
설명:

반환 된 값이 정수이지만 대답이 배열 인 이유가 혼란 스럽습니까?

입력 배열은 참조로 전달되므로 입력 배열에 대한 수정 사항도 호출자에게 알려집니다.

내부적으로 다음과 같이 생각할 수 있습니다.

// nums는 참조로 전달됩니다. (즉, 복사하지 않음)
int len = removeDuplicates (nums);

// 함수의 nums에 대한 수정 사항은 호출자가 알 수 있습니다.
// 함수에서 반환 한 길이를 사용하여 첫 번째 len 요소를 인쇄합니다.
for (int i = 0; i <len; i ++) {
print (nums [i]);
}

Hide Hint #1

In this problem, the key point to focus on is the input array being sorted. As far as duplicate elements are concerned, what is their positioning in the array when the given array is sorted? Look at the image above for the answer. If we know the position of one of the elements, do we also know the positioning of all the duplicate elements?

Hide Hint #2

We need to modify the array in-place and the size of the final array would potentially be smaller than the size of the input array. So, we ought to use a two-pointer approach here. One, that would keep track of the current element in the original array and another one for just the unique elements.

ought 1 [ɔ́:t]
조동사동사.1. [의무·도덕적 책임·당연·적당·필요] …해야 하다, …할 의무가 있다, …하는 것이 당연하다You ought to do it at once. = It ought to be done at once.그것은 당장 해야 한다.

Hide Hint #3

Essentially, once an element is encountered, you simply need to bypass its duplicates and move on to the next unique element.

힌트 # 1 숨기기
이 문제에서 집중해야 할 핵심은 정렬되는 입력 배열입니다. 중복 요소에 관한 한, 주어진 배열이 정렬 될 때 배열에서의 위치는 무엇입니까? 답은 위의 이미지를보십시오. 요소 중 하나의 위치를 알고 있다면 모든 중복 요소의 위치도 알고 있습니까?

힌트 # 2 숨기기
배열을 제자리에서 수정해야하며 최종 배열의 크기는 잠재적으로 입력 배열의 크기보다 작을 수 있습니다. 그래서 우리는 여기서 2 점 접근 방식을 사용해야합니다. 하나는 원래 배열의 현재 요소를 추적하고 다른 하나는 고유 한 요소 만 추적합니다.
힌트 # 3 숨기기
기본적으로 요소가 발견되면 중복 요소를 우회하고 다음 고유 요소로 이동하기 만하면됩니다.

Approach 1: Two Pointers

Algorithm

Since the array is already sorted, we can keep two pointers i and j, where i is the slow-runner while j is the fast-runner. As long as nums[i] = nums[j], we increment j to skip the duplicate.

When we encounter nums[j] \neq nums[i], the duplicate run has ended so we must copy its value to nums[i + 1]. i is then incremented and we repeat the same process again until j reaches the end of array.

public int removeDuplicates(int[] nums) {
    if (nums.length == 0) return 0;
    int i = 0;
    for (int j = 1; j < nums.length; j++) {
        if (nums[j] != nums[i]) {
            i++;
            nums[i] = nums[j];
        }
    }
    return i + 1;
}

Complexity analysis

Time complextiy : O(n). Assume that n is the length of array. Each of i and j traverses at most n steps.
Space complexity : O(1).

접근법 1 : 두 포인터
연산

배열이 이미 정렬 되었기 때문에 두 개의 포인터 ii와 jj를 유지할 수 있습니다. 여기서 ii는 느린 실행기이고 jj는 빠른 실행기입니다. nums [i] = nums [j] nums [i] = nums [j]이면 jj를 증가시켜 중복을 건너 뜁니다.

nums [j] \ neq nums [i] nums [j]를 만날 때


= nums [i], 중복 실행이 종료되었으므로 해당 값을 nums [i + 1] nums [i + 1]에 복사해야합니다. ii가 증분되고 jj가 배열의 끝에 도달 할 때까지 동일한 프로세스를 다시 반복합니다.

복잡성 분석

시간 복잡도 : O (n) . nn이 배열의 길이라고 가정합니다. ii 및 jj는 각각 최대 nn 단계를 횡단합니다.

공간 복잡성 : O (1) .

결과

class Solution {
    public int removeDuplicates(int[] nums) {
        if(nums ==null ||nums.length==0) return 0;
        int count =1;
        for(int i=1;i<nums.length;i++){
            if(nums[i]!=nums[i-1]) nums[count++]=nums[i];
        }
        return count;
    }
}

122. Best Time to Buy and Sell Stock II

leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/

Summary

We have to determine the maximum profit that can be obtained by making the transactions (no limit on the number of transactions done). For this we need to find out those sets of buying and selling prices which together lead to the maximization of profit.

Solution

Approach 1: Brute Force

In this case, we simply calculate the profit corresponding to all the possible sets of transactions and find out the maximum profit out of them.

Complexity Analysis

Time complexity : O(n^n). Recursive function is called n^n times.
Space complexity : O(n). Depth of recursion is n.

Approach 2: Peak Valley Approach

Algorithm

Say the given array is:

[7, 1, 5, 3, 6, 4].

If we plot the numbers of the given array on a graph, we get:

If we analyze the graph, we notice that the points of interest are the consecutive valleys and peaks.

Mathematically speaking: Total Profit= \sum_{i}(height(peak_i)-height(valley_i))

The key point is we need to consider every peak immediately following a valley to maximize the profit. In case we skip one of the peaks (trying to obtain more profit), we will end up losing the profit over one of the transactions leading to an overall lesser profit.

For example, in the above case, if we skip peak_i and valley_j trying to obtain more profit by considering points with more difference in heights, the net profit obtained will always be lesser than the one obtained by including them, since C will always be lesser than A+B.

Complexity Analysis

Time complexity : O(n). Single pass.
Space complexity : O(1). Constant space required.

Approach 3: Simple One Pass

Algorithm

This solution follows the logic used in Approach 2 itself, but with only a slight variation. In this case, instead of looking for every peak following a valley, we can simply go on crawling over the slope and keep on adding the profit obtained from every consecutive transaction. In the end,we will be using the peaks and valleys effectively, but we need not track the costs corresponding to the peaks and valleys along with the maximum profit, but we can directly keep on adding the difference between the consecutive numbers of the array if the second number is larger than the first one, and at the total sum we obtain will be the maximum profit. This approach will simplify the solution. This can be made clearer by taking this example:

[1, 7, 2, 3, 6, 7, 6, 7]

The graph corresponding to this array is:

From the above graph, we can observe that the sum A+B+C is equal to the difference D corresponding to the difference between the heights of the consecutive peak and valley.

같은날에 사고 팔수 없다는 제약 때문에 아래처럼 코드를 쓰면 안될것 같지만, 3,4,5,6에 사고 파는게 아니라 3에 사고 6에 파는것이다.

class Solution {
    public int maxProfit(int[] prices) {
        int maxprofit = 0;
        for (int i = 1; i < prices.length; i++) {
            if (prices[i] > prices[i - 1])
                maxprofit += prices[i] - prices[i - 1];
        }
        return maxprofit;
    }
}

Complexity Analysis

Time complexity : O(n). Single pass.
Space complexity: O(1). Constant space needed.

189. Rotate Array

leetcode.com/problems/rotate-array/

Summary

We have to rotate the elements of the given array k times to the right.

Solution

Approach 1: Brute Force

The simplest approach is to rotate all the elements of the array in k steps by rotating the elements by 1 unit in each step.

Complexity Analysis

Time complexity: \mathcal{O}(n \times k). All the numbers are shifted by one step(\mathcal{O}(n)) k times.
Space complexity: \mathcal{O}(1). No extra space is used.

Approach 2: Using Extra Array

Algorithm

We use an extra array in which we place every element of the array at its correct position i.e. the number at index i in the original array is placed at the index (i + k) \% \text{ length of array}. Then, we copy the new array to the original one.

Complexity Analysis

Time complexity: . One pass is used to put the numbers in the new array. And another pass to copy the new array to the original one.
Space complexity: . Another array of the same size is used.

Approach 3: Using Cyclic Replacements

Algorithm

We can directly place every number of the array at its required correct position. But if we do that, we will destroy the original element. Thus, we need to store the number being replaced in a temp variable. Then, we can place the replaced number(\text{temp}) at its correct position and so on, n times, where n is the length of array. We have chosen n to be the number of replacements since we have to shift all the elements of the array(which is n). But, there could be a problem with this method, if n \% k = 0 where k = k \% n (since a value of k larger than n eventually leads to a k equivalent to k \% n). In this case, while picking up numbers to be placed at the correct position, we will eventually reach the number from which we originally started. Thus, in such a case, when we hit the original number's index again, we start the same process with the number following it.

Now let's look at the proof of how the above method works. Suppose, we have n as the number of elements in the array and k is the number of shifts required. Further, assume n \%k = 0. Now, when we start placing the elements at their correct position, in the first cycle all the numbers with their index i satisfying i \%k = 0 get placed at their required position. This happens because when we jump k steps every time, we will only hit the numbers k steps apart. We start with index i = 0, having i \% k = 0. Thus, we hit all the numbers satisfying the above condition in the first cycle. When we reach back the original index, we have placed \frac{n}{k} elements at their correct position, since we hit only that many elements in the first cycle. Now, we increment the index for replacing the numbers. This time, we place other \frac{n}{k} elements at their correct position, different from the ones placed correctly in the first cycle, because this time we hit all the numbers satisfy the condition i \% k = 1. When we hit the starting number again, we increment the index and repeat the same process from i = 1 for all the indices satisfying i \% k == 1. This happens till we reach the number with the index i \% k = 0 again, which occurs for i=k. We will reach such a number after a total of k cycles. Now, the total count of numbers exclusive numbers placed at their correct position will be k \times \frac{n}{k} = n. Thus, all the numbers will be placed at their correct position.

Look at the following example to clarify the process:

nums: [1, 2, 3, 4, 5, 6] k: 2

돌다보면 언젠가는 출발자리로 오게된다는 원리.

class Solution {
  public void rotate(int[] nums, int k) {
    k = k % nums.length;
    int count = 0;
    for (int start = 0; count < nums.length; start++) {
      int current = start;
      int prev = nums[start];
      do {
        int next = (current + k) % nums.length;
        int temp = nums[next];
        nums[next] = prev;
        prev = temp;
        current = next;
        count++;
      } while (start != current);
    }
  }
}

Complexity Analysis

Time complexity: \mathcal{O}(n). Only one pass is used.
Space complexity: \mathcal{O}(1). Constant extra space is used.

Approach 4: Using Reverse

Algorithm

This approach is based on the fact that when we rotate the array k times, k%n elements from the back end of the array come to the front and the rest of the elements from the front shift backwards.

In this approach, we firstly reverse all the elements of the array. Then, reversing the first k elements followed by reversing the rest n-k elements gives us the required result.

Let n = 7 and k = 3.

Original List : 1 2 3 4 5 6 7 After reversing all numbers : 7 6 5 4 3 2 1 After reversing first k numbers : 5 6 7 4 3 2 1 After revering last n-k numbers : 5 6 7 1 2 3 4 --> Result

이건 아직 못봄.

class Solution {
  public void rotate(int[] nums, int k) {
    k %= nums.length;
    reverse(nums, 0, nums.length - 1);
    reverse(nums, 0, k - 1);
    reverse(nums, k, nums.length - 1);
  }
  public void reverse(int[] nums, int start, int end) {
    while (start < end) {
      int temp = nums[start];
      nums[start] = nums[end];
      nums[end] = temp;
      start++;
      end--;
    }
  }
}

Complexity Analysis

Time complexity: \mathcal{O}(n). n elements are reversed a total of three times.
Space complexity: \mathcal{O}(1). No extra space is used.

217. Contains Duplicate

leetcode.com/problems/contains-duplicate/

Approach #3 (Hash Table) [Accepted]

Intuition

Utilize a dynamic data structure that supports fast search and insert operations.

Algorithm

From Approach #1 we know that search operations is O(n) in an unsorted array and we did so repeatedly. Utilizing a data structure with faster search time will speed up the entire algorithm.

There are many data structures commonly used as dynamic sets such as Binary Search Tree and Hash Table. The operations we need to support here are search() and insert(). For a self-balancing Binary Search Tree (TreeSet or TreeMap in Java), search() and insert() are both O(\log n) time. For a Hash Table (HashSet or HashMap in Java), search() and insert() are both O(1) on average. Therefore, by using hash table, we can achieve linear time complexity for finding the duplicate in an unsorted array.

Java

public boolean containsDuplicate(int[] nums) { Set<Integer> set = new HashSet<>(nums.length); for (int x: nums) { if (set.contains(x)) return true; set.add(x); } return false; }

public boolean containsDuplicate(int[] nums) {
    Set<Integer> set = new HashSet<>(nums.length);
    for (int x: nums) {
        if (set.contains(x)) return true;
        set.add(x);
    }
    return false;
}

Complexity Analysis

Time complexity : O(n). We do search() and insert() for n times and each operation takes constant time.
Space complexity : O(n). The space used by a hash table is linear with the number of elements in it.

Note

For certain test cases with not very large n, the runtime of this method can be slower than Approach #2. The reason is hash table has some overhead in maintaining its property. One should keep in mind that real world performance can be different from what the Big-O notation says. The Big-O notation only tells us that for sufficiently large input, one will be faster than the other. Therefore, when n is not sufficiently large, an O(n) algorithm can be slower than an O(n \log n) algorithm.

See Also

136. Single Number

leetcode.com/problems/single-number/

비트마스크로 풀어야한다.

Approach 3: Math

Concept

2 * (a + b + c) - (a + a + b + b + c) = c

class Solution {
  public int singleNumber(int[] nums) {
    int sumOfSet = 0, sumOfNums = 0;
    Set<Integer> set = new HashSet();

    for (int num : nums) {
      if (!set.contains(num)) {
        set.add(num);
        sumOfSet += num;
      }
      sumOfNums += num;
    }
    return 2 * sumOfSet - sumOfNums;
  }
}

Complexity Analysis

Time complexity : O(n + n) = O(n). sum will call next to iterate through \text{nums}. We can see it as sum(list(i, for i in nums)) which means the time complexity is O(n) because of the number of elements(n) in \text{nums}.
Space complexity : O(n + n) = O(n). set needs space for the elements in nums

Approach 4: Bit Manipulation

Concept

If we take XOR of zero and some bit, it will return that bit
- a \oplus 0 = a
If we take XOR of two same bits, it will return 0
- a \oplus a = 0
a \oplus b \oplus a = (a \oplus a) \oplus b = 0 \oplus b = b

So we can XOR all bits together to find the unique number.

class Solution {
  public int singleNumber(int[] nums) {
    int a = 0;
    for (int i : nums) {
      a ^= i;
    }
    return a;
  }
}

Complexity Analysis

Time complexity : O(n). We only iterate through \text{nums}, so the time complexity is the number of elements in \text{nums}.
Space complexity : .

350. Intersection of Two Arrays II

leetcode.com/problems/intersection-of-two-arrays-ii/

Solution

If an interviewer gives you this problem, your first question should be - how should I handle duplicates? Your second question, perhaps, can be about the order of inputs and outputs. Such questions manifest your problem-solving skills, and help you steer to the right solution.

The solution for the previous problem, 349. Intersection of Two Arrays, talks about approaches when each number in the output must be unique. For this problem, we need to adapt those approaches so that numbers in the result appear as many times as they do in both arrays.

Approach 1: Hash Map

For the previous problem, we used a hash set to achieve a linear time complexity. Here, we need to use a hash map to track the count for each number.

We collect numbers and their counts from one of the arrays into a hash map. Then, we iterate along the second array, and check if the number exists in the hash map and its count is positive. If so - add the number to the result and decrease its count in the hash map.

It's a good idea to check array sizes and use a hash map for the smaller array. It will reduce memory usage when one of the arrays is very large.

Algorithm

If nums1 is larger than nums2, swap the arrays.
For each element in nums1:
- Add it to the hash map m.
  - Increment the count if the element is already there.
Initialize the insertion pointer (k) with zero.
Iterate along nums2:
- If the current number is in the hash map and count is positive:
  - Copy the number into nums1[k], and increment k.
  - Decrement the count in the hash map.
Return first k elements of nums1.

For our solutions here, we use one of the arrays to store the result. As we find common numbers, we copy them to the first array starting from the beginning. This idea is from this solution by sankitgupta.

public int[] intersect(int[] nums1, int[] nums2) {
    if (nums1.length > nums2.length) {
        return intersect(nums2, nums1);
    }
    HashMap<Integer, Integer> m = new HashMap<>();
    for (int n : nums1) {
        m.put(n, m.getOrDefault(n, 0) + 1);
    }
    int k = 0;
    for (int n : nums2) {
        int cnt = m.getOrDefault(n, 0);
        if (cnt > 0) {
            nums1[k++] = n;
            m.put(n, cnt - 1);
        }
    }
    return Arrays.copyOfRange(nums1, 0, k);
}

Complexity Analysis

Time Complexity: \mathcal{O}(n + m), where n and m are the lengths of the arrays. We iterate through the first, and then through the second array; insert and lookup operations in the hash map take a constant time.
Space Complexity: \mathcal{O}(\min(n, m)). We use hash map to store numbers (and their counts) from the smaller array.

Approach 2: Sort

You can recommend this method when the input is sorted, or when the output needs to be sorted. Here, we sort both arrays (assuming they are not sorted) and use two pointers to find common numbers in a single scan.

Algorithm

Sort nums1 and nums2.
Initialize i, j and k with zero.
Move indices i along nums1, and j through nums2:
- Increment i if nums1[i] is smaller.
- Increment j if nums2[j] is smaller.
- If numbers are the same, copy the number into nums1[k], and increment i, j and k.
Return first k elements of nums1.

public int[] intersect(int[] nums1, int[] nums2) {
    Arrays.sort(nums1);
    Arrays.sort(nums2);
    int i = 0, j = 0, k = 0;
    while (i < nums1.length && j < nums2.length) {
        if (nums1[i] < nums2[j]) {
            ++i;
        } else if (nums1[i] > nums2[j]) {
            ++j;
        } else {
            nums1[k++] = nums1[i++];
            ++j;
        }
    }
    return Arrays.copyOfRange(nums1, 0, k);
}

Complexity Analysis

Time Complexity: , where n and m are the lengths of the arrays. We sort two arrays independently, and then do a linear scan.
Space Complexity: from to , depending on the implementation of the sorting algorithm. For the complexity analysis purposes, we ignore the memory required by inputs and outputs.

Approach 3: Built-in Intersection

only c++

This is similar to Approach 2. Instead of iterating with two pointers, we use a built-in function to find common elements. In C++, we can use set_intersection for sorted arrays (or multisets).

The retainAll method in Java, unfortunately, does not care how many times an element occurs in the other collection. You can use the retainOccurrences method of the multiset implementation in Guava.

Algorithm

Note that set_intersection returns the position past the end of the produced range, so it can be used as an input for the erase function. The idea is from this solution by StefanPochmann.

vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
    sort(begin(nums1), end(nums1));
    sort(begin(nums2), end(nums2));
    nums1.erase(set_intersection(begin(nums1), end(nums1),
        begin(nums2), end(nums2), begin(nums1)), end(nums1));
    return nums1;
}

Complexity Analysis

Same as for approach 2 above.

Follow-up Questions

What if the given array is already sorted? How would you optimize your algorithm?
- We can use either Approach 2 or Approach 3, dropping the sort of course. It will give us linear time and constant memory complexity.
What if nums1's size is small compared to nums2's size? Which algorithm is better?
- Approach 1 is a good choice here as we use a hash map for the smaller array.
What if elements of nums2 are stored on disk, and the memory is limited such that you cannot load all elements into the memory at once?
- If nums1 fits into the memory, we can use Approach 1 to collect counts for nums1 into a hash map. Then, we can sequentially load and process nums2.
- If neither of the arrays fit into the memory, we can apply some partial processing strategies:
  - Split the numeric range into subranges that fits into the memory. Modify Approach 1 to collect counts only within a given subrange, and call the method multiple times (for each subrange).
  - Use an external sort for both arrays. Modify Approach 2 to load and process arrays sequentially.

지정된 배열이 이미 정렬되어 있으면 어떻게 하시겠습니까? 알고리즘을 어떻게 최적화하시겠습니까?
- 우리는 어프로치 2나 어프로치 3 중 하나를 사용할 수 있고, 어떤 종류의 진로를 포기할 수 있다. 그것은 우리에게 선형적인 시간과 지속적인 기억의 복잡성을 줄 것이다.
만약 숫자1의 크기가 숫자2의 크기에 비해 작다면? 어떤 알고리즘이 더 좋은가?
- 작은 배열에 해시 맵을 사용하기 때문에 접근법 1은 여기서 좋은 선택이다.
nums2의 요소가 디스크에 저장되어 있고 메모리가 제한되어 있어서 모든 요소를 메모리에 한 번에 로드할 수 없다면?
- nums1이 메모리에 맞으면, 접근법 1을 사용하여 nums1의 카운트를 해시 맵으로 수집할 수 있다. 그러면 순차적으로 Nums2 로딩해서 처리할 수 있어.
- 두 어레이 중 어느 어레이도 메모리에 맞지 않을 경우 일부 처리 전략을 적용할 수 있다.
  - 숫자 범위를 메모리에 맞는 하위 범위로 분할하십시오. 지정된 하위 범위 내에서만 카운트를 수집하려면 접근법 1을 수정하고 각 하위 범위에 대해 메소드를 여러 번 호출하십시오.두 어레이 모두에 대해 외부 정렬을 사용하십시오.
  - 접근법 2를 수정하여 어레이를 순차적으로 로드 및 처리하십시오.

66. Plus One

leetcode.com/problems/plus-one/

이 코드를 짜는것은 쉽다. 그러나 솔루션 코드처럼 깔끔하게 짤 수 있어야 한다.

class Solution {
  public int[] plusOne(int[] digits) {
    int n = digits.length;

    // move along the input array starting from the end
    for (int idx = n - 1; idx >= 0; --idx) {
      // set all the nines at the end of array to zeros
      if (digits[idx] == 9) {
        digits[idx] = 0;
      }
      // here we have the rightmost not-nine
      else {
        // increase this rightmost not-nine by 1 
        digits[idx]++;
        // and the job is done
        return digits;
      }
    }
    // we're here because all the digits are nines
    digits = new int[n + 1];
    digits[0] = 1;
    return digits;
  }
}

283. Move Zeroes

leetcode.com/problems/move-zeroes/

예쁜 코드를 짤 수 있는가?

class Solution {
    public void moveZeroes(int[] nums) {
        int numIdx = 0;
        
        for(int searchIdx = 0; searchIdx < nums.length; searchIdx++){
            if(nums[searchIdx] != 0){
                int foundNum = nums[searchIdx];
                nums[searchIdx] = nums[numIdx];
                nums[numIdx] = foundNum;
                numIdx++;
            }
        }        
    }
}

1. Two Sum

leetcode.com/problems/two-sum/

해쉬테이블의 정석

Solution

Approach 1: Brute Force

The brute force approach is simple. Loop through each element x and find if there is another value that equals to target - x.

Complexity Analysis

Time complexity : O(n^2). For each element, we try to find its complement by looping through the rest of array which takes O(n) time. Therefore, the time complexity is O(n^2).
Space complexity : O(1).

Approach 2: Two-pass Hash Table

To improve our run time complexity, we need a more efficient way to check if the complement exists in the array. If the complement exists, we need to look up its index. What is the best way to maintain a mapping of each element in the array to its index? A hash table.

We reduce the look up time from O(n) to O(1) by trading space for speed. A hash table is built exactly for this purpose, it supports fast look up in near constant time. I say "near" because if a collision occurred, a look up could degenerate to O(n) time. But look up in hash table should be amortized O(1) time as long as the hash function was chosen carefully.

A simple implementation uses two iterations. In the first iteration, we add each element's value and its index to the table. Then, in the second iteration we check if each element's complement (target - nums[i]) exists in the table. Beware that the complement must not be nums[i] itself!

Complexity Analysis:

Time complexity : . We traverse the list containing n elements exactly twice. Since the hash table reduces the look up time to O(1), the time complexity is O(n).
Space complexity : O(n). The extra space required depends on the number of items stored in the hash table, which stores exactly n elements.

Approach 3: One-pass Hash Table

It turns out we can do it in one-pass. While we iterate and inserting elements into the table, we also look back to check if current element's complement already exists in the table. If it exists, we have found a solution and return immediately.

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer,Integer> map = new HashMap<Integer,Integer>();
        for(int i=0; i< nums.length; i++){
            int num=target-nums[i];
            if(map.containsKey(num)){
                return new int[] {map.get(num),i};
            }
            map.put(nums[i],i);
        }
        throw new IllegalArgumentException("No two sum solution");
    }
}

Complexity Analysis:

Time complexity : . We traverse the list containing n elements only once. Each look up in the table costs only time.
Space complexity : O(n). The extra space required depends on the number of items stored in the hash table, which stores at most elements.

36. Valid Sudoku [Medium]

leetcode.com/problems/valid-sudoku/

Solution

Intuition

The naive solution would be to iterate three times over the board to ensure that :

There is no rows with duplicates.
There is no columns with duplicates.
There is no sub-boxes with duplicates.

Actually, all this could be done in just one iteration.

Approach 1: One iteration

Let's first discuss two questions.

How to enumerate sub-boxes?

One could use box_index = (row / 3) * 3 + col / 3 where / is an integer division, row is a row number, and col is a column number.

How to ensure that there is no duplicates in a row / column / box?

One could just track all values which were already encountered in a hash map value -> count.

Now everything is ready for the overall algorithm :

Move along the board.
- Check for each cell value if it was seen already in the current row / column / box :
  - Return false if yes.
  - Keep this value for a further tracking if no.
Return true.

이건 그냥 스도쿠 밸리데이션 체커라서 겁먹을 필요 없다. 해쉬테이블만 쓸줄알면 아주 쉽게 풀수 있다.

진짜 스도쿠는 여기에..

leetcode.com/problems/sudoku-solver/

class Solution {
  public boolean isValidSudoku(char[][] board) {
    // init data
    HashMap<Integer, Integer> [] rows = new HashMap[9];
    HashMap<Integer, Integer> [] columns = new HashMap[9];
    HashMap<Integer, Integer> [] boxes = new HashMap[9];
    for (int i = 0; i < 9; i++) {
      rows[i] = new HashMap<Integer, Integer>();
      columns[i] = new HashMap<Integer, Integer>();
      boxes[i] = new HashMap<Integer, Integer>();
    }

    // validate a board
    for (int i = 0; i < 9; i++) {
      for (int j = 0; j < 9; j++) {
        char num = board[i][j];
        if (num != '.') {
          int n = (int)num;
          int box_index = (i / 3 ) * 3 + j / 3;

          // keep the current cell value
          rows[i].put(n, rows[i].getOrDefault(n, 0) + 1);
          columns[j].put(n, columns[j].getOrDefault(n, 0) + 1);
          boxes[box_index].put(n, boxes[box_index].getOrDefault(n, 0) + 1);

          // check if this value has been already seen before
          if (rows[i].get(n) > 1 || columns[j].get(n) > 1 || boxes[box_index].get(n) > 1)
            return false;
        }
      }
    }

    return true;
  }
}

Complexity Analysis

Time complexity : \mathcal{O}(1) since all we do here is just one iteration over the board with 81 cells.
Space complexity : \mathcal{O}(1).

48. Rotate Image

leetcode.com/problems/rotate-image/

Solution

Approach 1 : Transpose and then reverse

The obvious idea would be to transpose the matrix first and then reverse each row. This simple approach already demonstrates the best possible time complexity \mathcal{O}(N^2). Here is a visualization of why this approach works on a sample matrix.

Time complexity : \mathcal{O}(N^2).
Space complexity : \mathcal{O}(1) since we do a rotation in place.

Approach 2 : Rotate four rectangles

Intuition

Approach 1 makes two passes through the matrix, though it's possible to make a rotation in one pass.

To figure out how let's check how each element in the angle moves during the rotation.

That gives us an idea to split a given matrix in four rectangles and reduce the initial problem to the rotation of these rectangles.

Now the solution is quite straightforward - one could move across the elements in the first rectangle and rotate them using a temp list of 4 elements.

Implementation

1 / 6

class Solution {
  public void rotate(int[][] matrix) {
    int n = matrix.length;
    for (int i = 0; i < n / 2 + n % 2; i++) {
      for (int j = 0; j < n / 2; j++) {
        int[] tmp = new int[4];
        int row = i;
        int col = j;
        for (int k = 0; k < 4; k++) {
          tmp[k] = matrix[row][col];
          int x = row;
          row = col;
          col = n - 1 - x;
        }
        for (int k = 0; k < 4; k++) {
          matrix[row][col] = tmp[(k + 3) % 4];
          int x = row;
          row = col;
          col = n - 1 - x;
        }
      }
    }
  }
}

Complexity Analysis

Time complexity : \mathcal{O}(N^2) is a complexity given by two inserted loops.
Space complexity : \mathcal{O}(1) since we do a rotation in place and allocate only the list of 4 elements as a temporary helper.

Approach 3 : Rotate four rectangles in one single loop

The idea is the same as in the approach 2, but everything is done in one single loop and hence it's a way more elegant (kudos go to @gxldragon).

Here is a visualization for the above code.

이 방법으로 풀었다. 이미지가 사각형이라는 사실을 이용하면 쉽다.

class Solution {
  public void rotate(int[][] matrix) {
    int n = matrix.length;
    for (int i = 0; i < (n + 1) / 2; i ++) {
      for (int j = 0; j < n / 2; j++) {
        int temp = matrix[n - 1 - j][i];
        matrix[n - 1 - j][i] = matrix[n - 1 - i][n - j - 1];
        matrix[n - 1 - i][n - j - 1] = matrix[j][n - 1 -i];
        matrix[j][n - 1 - i] = matrix[i][j];
        matrix[i][j] = temp;
      }
    }
  }
}

Time complexity : \mathcal{O}(N^2) is a complexity given by two inserted loops.
Space complexity : \mathcal{O}(1) since we do a rotation in place.