Inertia

largest rectangle in histogram

Given n non-negative integers representing the histogram’s bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

Given heights = [2,1,5,6,2,3],
return 10.

idea

naive는 start, end 를 하나씩 정해서 돌면 O(N^2).

모든 height의 왼쪽, 오른쪽 바운더리를 알면 맥스 값을 구할 수 있다. 왼쪽/오른쪽 바운더리는 자신보다 낮은 바를 만나면 결정된다. 따라서 ascending 순으로 리스트를 관리하다가 낮은 바가 나오면 오른쪽 바운더리는 결정이 되고, 왼쪽 바운더리는 리스트의 tail이 된다. 이렇게 각 height에 따라서 계산을 하면 최적해를 구할 수 있다. 이 리스트는 스택으로 구현하는 것이 좋고, push, pop, top 정도만 필요하므로.

위의 예제를 기반으로 시뮬레이션 해보면 [2,1,5,6,2,3]

i stack desc
0 0
1 0 n[i](1)< stack.top(2), stack의 탑인 2의 right는 1, left는 -1(stack이 empty이므로). left right 경계는 포함되지 않으므로 width = 1-(-1)-1 = 1이 됨. localMax=2*1=2
1 1
2 1,2
3 1,2,3
4 1,2 stack pop. poped=3. n[3]=6. 6의 right=4, left=2. width=4-2-1=1. localMax=6*1=6
4 1 stack pop, poped=2, n[2]=5, 5의 right=4, left=1. width=4-1-1=2. localMax=5*2=10
4 1,4
5 1,4,5
6 1,4 stack pop, poped=5, n[5]=3, 3의 right=6, left=4. width=6-4-1=1. localMax=3*1=3
6 1 stack pop, poped=4, n[4]=2, 2의 right=6, left=1, width=6-1-1=4. localMax=2*4=8
6 stack pop, poped=1, n[1]=1, 1의 right=6, left=-1, width=6-(-1)-1. localMax=1*6=6

따라서 largest area는 10이 된다.

implementation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int largestRectangleArea(int[] heights) {
    int max = Integer.MIN_VALUE;
    Stack<Integer> stack = new Stack<>();
    for(int i=0;i<=N;i++){ // interate until N,
        int h = i==N?0:heights[i];
        if(stack.isEmpty() || h >= heights[stack.peek()])
            stack.push(i);
        else{
            h=heights[stack.pop()];
            int width = stack.isEmpty() ? i : i-stack.peek()-1;
            max=Math.max(max, h*width);
            i--;
        }
    }
    return max;
}

problems

reference

maximal square 

1
2
3
4
5
6
7
8
9
Given a 2D binary matrix filled with 0's and 1's, find the largest square containing only 1's and return its area.

For example, given the following matrix:

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
Return 4.

idea

생각하기 어려운 dp 식일것 같은데, 아래 처럼 된다. dp(i,j)를 i,j에서 끝나는 maximal square라고 정의.

dp(i,j) = Math.min(dp(i-1,j), dp(i,j-1), dp(i-1,j-1))+1

1인 셀이면 dp(i,j)=1이 된다. 이웃들중의 가장 작은 값+1이 되는 것이다. 즉, 모두 인접한 이전 값들이 모두 1이라야 자신은 2가 될 수 있다.

initial condtion은 (x,0) 은 1이면 1, 아니면 0이 된다. (0,y)도 마찬가지이다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public int maximalSquare(char[][] matrix) {
        int row=matrix.length;
        if(row==0) return 0;
        int col = matrix[0].length;

        int ret=0;
        int[][] dp = new int[row][col];
        for(int y=0;y<row;y++){
            if(matrix[y][0]=='1'){
                dp[y][0]=1;
                ret=1;
            }
        }

        for(int x=0;x<col;x++){
            if (matrix[0][x]=='1'){
                dp[0][x]=1;
                ret=1;
            }
        }

        for (int y = 1; y < row; y++) {
            for (int x = 1; x < col; x++) {
                if(matrix[y][x]=='0') continue;
                dp[y][x] = Math.min(dp[y-1][x], Math.min(dp[y-1][x-1], dp[y][x-1]) ) +1;
                if(dp[y][x]>ret)
                    ret = dp[y][x];
            }
        }

        return ret*ret; // return area
    }

problems

next permutation 

1
2
3
4
5
6
7
8
9
10
Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).

The replacement must be in-place, do not allocate extra memory.

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

idea

idea는 큰 숫자를 찾아서 앞으로 보내줘야 하는데 해당 수를 찾는게 첫번째. 그렇게 하려면 끝에서 부터 이동하면서 a[i-1]<a[i] 을 만족하는 위치(i)를 찾고, i와 바꾸게 될 인덱스 j를 찾는다. a[i:N]까지는 descending이므로 a[i-1]보다 크면서 가장 작은 a[j]를 선택하고 swap한다. 그후 a[i:N]을 reverse하게 되면 next permutation이 된다.

아래 예를 보자. 4->9가 처음으로 증가하는 부분이고, 4보다 큰 값은 7이 선택되었다. 그러면 다시 9,8,4,1이 되는데 역시 descding 이다. 그러니 이것을 가장 작은 수로 바꾸려면 reverse인, 1,4,8,9로 바꿔주면 된다.

1
2
[6，3，4，9，8，7，1] -> [6, 3, 7, 1, 4, 8, 9]
     i-1 i    j
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void nextPermutation(int[] nums){
    int n = nums.length;
    if(n<=1) return;
    // find first pos nums[i-1]< nums[i] from the end
    int i=n-1;
    for (; i >=1; i--) {
        if( nums[i-1] < nums[i])
            break;
    }

    // find min but greater than nums[i-1]
    // we can use descending order property to find j
    int j = nums.length-1;
    for (; j >i; j--) {
        if (nums[i-1]< nums[j]){
            break;
        }
    }
    swap(nums, i-1, j);

    // still descending order from nums[i] to the end
    reverse(nums, i);
}

problems

reference

intergral image

algorithm 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Given a matrix A, write a matrix M for which every element [i,j] is the sum of all elements of A left and above A[i,j]
Considering the following matrix A:

[
  [3, 7, 1],
  [2, 4, 0],
  [9, 4, 2]
]
Compute M:

[
  [3,  10, 11],
  [5,  16, 17],
  [14, 29, 32]
]

dp

M(i,j)= M(i-1, j) + M(i, j-1) - M(i-1,j-1) + A(i,j)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void integralImage(int[][] m){
    int row = m.length;
    int col = m[0].length;

    for (int y = 0; y < row; y++) {
        for (int x = 0; x < col; x++) {
            if(x==0 && y==0) continue;
            else if(x==0){
                m[y][x] += m[y-1][x];
            }else if(y==0)
                m[y][x] += m[y][x-1];
            else{
                m[y][x] += m[y-1][x] + m[y][x-1] - m[y-1][x-1];
            }
        }
    }
}

problems

reference

longest increasing subsequence

아래 문제를 보자.

1
2
3
4
5
6
7
8
9
Given an unsorted array of integers, find the length of longest increasing subsequence.

For example,
Given [10, 9, 2, 5, 3, 7, 101, 18],
The longest increasing subsequence is [2, 3, 7, 101], therefore the length is 4. Note that there may be more than one LIS combination, it is only necessary for you to return the length.

Your algorithm should run in O(n2) complexity.

Follow up: Could you improve it to O(n log n) time complexity?

N^2 with dp

L(i)= i부터 시작해서 끝까지의 lis 라고 정의 하면 L(i-1)=L(i)+1 if a(i-1)<a(i)의 식이 성립한다. 따라서 아래처럼 구현.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int lis_dp(int[] a){
       int N = a.length;
       if(N==0) return 0;

       int[] dp = new int[N];
       int ret =1;
       for(int i=N-1;i>=0;i--){
           dp[i]=1;
           for(int j=i+1;j<N;j++){
               if(a[i]<a[j]){
                   dp[i] =Math.max(dp[i], dp[j]+1);
               }
           }
           ret=Math.max(ret, dp[i]);
       }

       return ret;
   }

binary search를 사용하면 nlogN도 가능하다. sorted array를 유지하면서 하나씩 추가하는데, tail보다 큰 수가 들어오면 tail에 추가하고, 그 이하의 값이 들어오면 기존 값을 binary search를 이용해서 insertion point에 업데이트 한다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int lis(int[] a){
       int N = a.length;
       if(N==0) return 0;

       int[] dp = new int[N];
       int ret=1;
       int last=0;
       dp[0]=a[0];
       for(int i=0;i<N;i++){
           if(dp[last]<a[i]) {
               dp[++last]=a[i];
               ret = last+1;
               continue;
           }
           int pos = bisect(dp, 0, last, a[i]);
           dp[pos]=a[i];
       }
       return ret;
   }

problems

reference

binary indexed tree

algorithm

binary indexed tree(bit)는 Segment tree처럼 range sum을 구하는 것에 최적화된 알고리즘이지만, segment tree보다 구현이 훨씬 쉽다. 대신 이해는 좀 더 여렵다. 그래서 segment tree는 이제 안녕.

time complexity
construction O(NlogN)
sum O(logN)
update O(logN)

idea

integer는 2^n승의 조합으로 표현할 수 있는것처럼, cumulative sum도 그렇게 나타낼 수 있겠다는 것.
2진수 표현에서 착안.
tree(i) = sum from i-2^r+1 to i
라고 정의 r은 i를 2진수로 나타내었을때 마지막 1이 있는 자리수. 0b10은 1, 0b1은 0

아래 7개 원소를 가지는 배열이 있고 cumulative sum을 계산하게 되면 아래표와 같다. 

1
2
3
idx     1   2   3   4   5   6   7
n[i]    1   3   2   2   4   7   2
cul sum 1   4   6   8   12  19  21

이것을 tree로 표현하는데, parent node는 left child node의 cumulative sum을 가지고 있게 설계를 하면 다음 트리와 같은 모양이 나온다.

  • 4는 [1-4] 모든 값을 합
  • 2는 1과 2의 합
  • 3은 3만
  • 5는 5만 
1
2
3
4
5
6
            4[100]
              +8
    2[010]             6[110]
     +4                  +11
1[001]  3[011]    5[101]    7[111]
+1          +2         +4        +2

그렇다면 여기서 더 응용을 해서,

  • 5까지의 누적 합을 구하고 싶으면, 노드 5와 노드4를 더하면 되고
  • 6까지의 누적 합을 구하고 싶으면, 노드 6(5-6)과 노드4(1-4)를 더하면 된다.

공교롭게도, 이 모든 것은 last 1bit를 빼주면서 계속 반복해주면 된다. last 1bit는 i&-i로 구할 수 있다.
이것을 예로 들어보면 아래처럼 될 수 있다.

1
2
3
4
6[110] 의 경우
    6[110],     [5-6]까지의 합. -> 010을 빼줌
    4[100],     [1-4]까지의 합, -> 100을 빼줌
    0. 종료.

2D

problems

reference

binary search

algorithm

sorted array에서 타겟값을 찾는것. 반으로 나누어서 탐색공간을 1/2씩 줄여서 O(logN)만에 원하는 값을 찾을 수 있음. 엄청나게 느리게 증가하는 것임. 70억개중 하나 찾는 것은 33번만의 분기만에 찾을 수 있음.

basic

아래가 기본형 binary search이다. sorted array a에서 target값을 찾는 것이며 없으면 -1을 리턴하는 기본형.

기본적인 로직.

  1. a[mid] > target, target이 왼쪽에 있음. -> hi를 mid-1로 치환
  2. a[mid] < target, target값이 오른쪽에 있음. -> lo를 mid+1로 치환
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
   int binarySearch(int target, int[] a){
	int lo = 0;
	int hi = a.length - 1;
	while (lo<=hi) { // notice = is there.
		int mid = lo + (hi-lo)/2; // to prevent overflow, (hi-lo) used
		if (a[mid] > target ) {
			hi = mid-1;
		}else if (a[mid] < target) {
			lo = mid + 1;
		}else{
			return mid;
		}
	}

	return -1;
}

lower bound

1, 2, 3, 4, 4, 4, 7, 8, 9, 10

이제 첫번째 변형. 배열 a에서 중복되는 값이 있을 수 있고 이중에서 가장 첫번째(왼쪽) 값을 찾는다고 생각해보자. 어떻게 변형해야 할까.

기본적으로 (2)는 기본형과 동일하지만 1/3번째가 아래처럼 바뀜.

  1. a[mid] > target, target이 왼쪽에 있음. -> hi를 mid로 치환. 여기서 -1을 하지 않는 이유는 target값이 배열의 최소값보다 작으면 index underflow가 나기 때문임.
  2. a[mid] < target, target값이 오른쪽에 있음. -> lo를 mid+1로 치환
  3. a[mid] == target, hi를 mid로 치환.
    1. mid의 왼쪽에 동일값이 있을 수 있으므로 오른쪽을 버리지만 한편으로 이것이 마지막 target값일 수도 있으니 -1을 더하진 않음.
1
2
3
4
5
6
7
8
9
10
11
12
int lowerBound(int lo, int hi, int[] a, int key){
	while (lo<hi) {
		int mid = lo + (hi-lo)/2;
		if (a[mid] < key) {
			lo = mid+1;
		}else{
			hi = mid;
		}
	}
       if(a[lo]==key) return lo;
       return -1;
}

uppper bound

1, 2, 3, 4, 4, 4, 7, 8, 9, 10

이제 lower_bound와 반대로, 배열 a에서 중복되는 값이 있을 수 있고 이중에서 가장 마지막(오른쪽) 값을 찾는다고 생각해보자. 어떻게 변형해야 할까.

(1)는 기본형과 동일하지만 2/3번째가 아래처럼 바뀜.

  1. a[mid] > target, target이 왼쪽에 있음. -> hi를 mid-1로 치환.
  2. a[mid] < target, target값이 오른쪽에 있음. -> lo를 mid로 치환. mid+1로 치환하지 않는 이유는 index overflow가 나기 때문임.
  3. a[mid] == target, lo를 mid로 치환.
    1. mid의 오른쪽에 동일값이 있을 수 있으므로 왼쪽을 버리지만 한편으로 이것이 마지막 target값일 수도 있으니 +1을 더하진 않음.
1
2
3
4
5
6
7
8
9
10
11
12
int upperBound(int lo, int hi, int[] a, int key){
	while (lo<hi) {
		int mid = lo+(hi-lo+1)/2;
		if (a[mid]>key){
               hi = mid-1;
           }else{
			lo = mid;
		}
	}
       if(a[lo]==key) return lo;
       return -1;
}

in a rotated array

{5,6,7,8,1,2,3} 처럼 한번 rotated된 배열에서 특정 숫자를 찾는다고 생각해보자. 이때에도 바이너리 서치를 사용할 수 있을까? 답은 예스. 반으로 잘랐을때 왼쪽과 오른쪽 하나는 ascending이므로 이 것을 이용해서 target이 왼쪽에 있는지 오른쪽에 있는지 판단할 수 있다!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
static int bsearchRotatedSimpler(int[] a, int key){
    int lo = 0;
    int hi = a.length-1;
    while(lo<=hi){
        int m = (lo+hi)/2;
        if(key==a[m]) return m;

        if(a[lo]<=a[m]){
            if(a[lo] <= key && key <= a[m])
                hi=m-1;
            else lo=m+1;
        }else{
            if(a[m] <=key && key <=a[hi])
                lo=m+1;
            else hi=m-1;
        }
    }

    return -1;
}

problems

reference

history

  • 11/28/2016 , binarySearchRotatedArray/searchRange added
  • 11/7/2017, lowerBound/upperBound added

Maximum XOR

아래 문제를 보자

1
2
3
4
5
6
7
8
9
10
Given a non-empty array of numbers, a0, a1, a2, … , an-1, where 0 ≤ ai < 231.
Find the maximum result of ai XOR aj, where 0 ≤ i, j < n.
Could you do this in O(n) runtime?

Example:
Input: [3, 10, 5, 25, 2, 8]

Output: 28

Explanation: The maximum result is 5 ^ 25 = 28.

위 문제는 naive하게는 두원소를 가면서 매번 XOR를 해서 max를 구하면 된다. 이것은 O(N^2). 구현은 생략.

idea

먼저 하나의 bit만 생각해보자. n번째 bit a^b=1이 되려면 1과 0이 둘다 있어야 한다. 그런데 xor는 a^b=c <==> a^c=b이 성립한다. 그러면 원래의 식은 a^1=b이 되고 각 수를 masking해서 나온 수를 set에 저장하고, 그것을 mask와 xor한 값이 그 set에 있으면 우리는 n번째 bit수를 1로 만들 수 있다는 얘기다.

아래 구현 참고.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public int findMaximumXOR(int[] nums) {
        int N = nums.length;
        int mask=0;
        int max=0;
        for(int i=30;i>=0;i--){
            mask |= (1<<i);
            Set<Integer> set = new HashSet<>(); // prefix
            for(int n:nums){
                set.add(n&mask);
            }

            // now find out if there are two prefix with different i-th bit
            // if there is, the new max should be current max with one 1 bit at i-th position, which is candidate
            // and the two prefix, say A and B, satisfies:
            // A ^ B = candidate
            // so we also have A ^ candidate = B or B ^ candidate = A
            // thus we can use this method to find out if such A and B exists in the set
            int temp = max | (1<<i);
            for(int prefix: set){
                if(set.contains(prefix^temp) ){
                    max=temp;
                    break;
                }
            }
        }
        return max;
    }

Problems

kadane 2D

이전 포스트에서 kadane algorithm을 소개했었는데 이번에는 2D matrix 확장. 아래 문제를 보자.

1
2
3
4
5
6
7
8
9
Given a 2D array, find the maximum sum submatrix in it.

example>
{ 1,  2, -1, -4, -20},
{-8, -3,  4,  2,   1},
{ 3,  8, 10,  1,   3},
{-4, -1,  1,  7,  -6}

위의경우, (1,1)에 있는 -3부터 (3,3)에 있는 7까지의 submatrix가 최대 합이된다.

naive

(start x, start y), (end x, end y)를 바꿔가면서 하면 for loop 4번. time complexity는 O(N^4)가 된다.

kadane 2D

kadane으로 1d array를 O(N^2)에서 O(N)으로 만들었듯이, 2D는 O(N^4)를 O(N^3)으로 만들 수 있다. left, right좌표를 옮겨가면서 row를 kadane 알고리즘을 적용하면 된다. 이때 column 값들을 accumulate하면서 하면 더 효율적으로 할 수 있는데 아래 코드를 보면 이해가 갈듯.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
int kadane2d(int[][] m){
    int row = m.length;
    if(row==0)return 0;
    int col = m[0].length;

    int ret = Integer.MIN_VALUE;
    for (int left = 0; left < col; left++) {
        int[] sum = new int[row]; // reuse this 
        for (int right = left; right < col; right++) {
            for (int i = 0; i < row; i++) {
                sum[i] += m[i][right];
            }

            int curMax=sum[0];
            int max=sum[0];
            for (int i = 1; i < row; i++) {
                curMax = Math.max(curMax+sum[i], sum[i]);
                max = Math.max(curMax, max);
            }
            ret=Math.max(ret, max);
        }
    }

    return ret;
}

Problems

Reference

search sorted 2d matrix

algorithm

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

Integers in each row are sorted in ascending from left to right.
Integers in each column are sorted in ascending from top to bottom.

1
2
3
4
5
[1,   4,  7, 11, 15]
[2,   5,  8, 12, 19]
[3,   6,  9, 16, 22]
[10, 13, 14, 17, 24]
[18, 21, 23, 26, 30]

문제 출처, search 2d matrix 2 @leetcode

binary search를 사용하면 각 row에서 log(col)만에 target이 있는지 없는지 판단 가능. 즉, O(col*log(row))의 time complexity.

Linear

더 잘 할 수도 있는데, O(row+col) 만에 가능함.

top right 코너에서 왼쪽으로 가면 작은값, 오른쪽으로 가면 큰 값이다. 따라서, 한번 이동할때마다 row나 컬럼을 탐색공간에서 제거할 수 있다. 같은 방식으로 bottom left 코너에서도 가능. 하지만 top left나 bottom right에서는 불가능함. 그 이유는 모두 증가하는 방향이기 때문임.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public boolean searchMatrix_linear(int[][] matrix, int target) {
        int row = matrix.length;
        if(row==0) return false;
        int col = matrix[0].length;

        int r = 0;
        int c =col-1;
        while(r<row&&c>=0){
            if(matrix[r][c]==target ) return true;
            else if (matrix[r][c]>target) c--;
            else if (matrix[r][c]<target) r++;
        }
        return false;
}

About

Etiam porta sem malesuada magna mollis euismod. Cras mattis consectetur purus sit amet fermentum. Aenean lacinia bibendum nulla sed consectetur.

Categories

Tags

Tag Cloud

CVA algorithm angular aws c++ checkstyle cloud architecture coverage design django docker dp dynamo elasticsearch emacs emr fzf general gerrit git github google graph hadoop hexo invoke jacoco java jekyll jenkins kibana mailchimp maven mgmt mockito mybatis mysql nosql oauth proxy rake regex rest ripgrep ruby spark spring in action spring in actions sql ssh swagger system design template tmux tree vscode wordgrep zeppelin

Archives

Recents