C] leetCode 2540 - Minimum Common Value (+ Two Pointers)

 

 

리트코드 2540 문제

 

Given two integer arrays nums1 and nums2, sorted in non-decreasing order, return the minimum integer common to both arrays. If there is no common integer amongst nums1 and nums2, return -1.

Note that an integer is said to be common to nums1 and nums2 if both arrays have at least one occurrence of that integer.

 

 

Example 1:

• Input: nums1 = [1,2,3], nums2 = [2,4]
• Output: 2
• Explanation: The smallest element common to both arrays is 2, so we return 2.

 

 

Example 2:

• Input: nums1 = [1,2,3,6], nums2 = [2,3,4,5]
• Output: 2
• Explanation: There are two common elements in the array 2 and 3 out of which 2 is the smallest, so 2 is returned.

 

 

Constraints:

• 1 <= nums1.length, nums2.length <= 105
• 1 <= nums1[i], nums2[j] <= 109
• Both nums1 and nums2 are sorted in non-decreasing order.

 

오름차순으로 정렬된 두 배열에서 제일 처음 등장하는 common value를 찾는 문제이다.

 

두 배열의 첫번째 인덱스에서 시작해서 값이 같으면 바로 리턴하고, 값이 같지 않으면 둘 중 값이 더 적은 쪽의 배열 인덱스를 한칸 증가하면서 둘 중 한 배열의 끝의 도달할 때까지 반복하며 검사하면 된다.

 

 

이러한 풀이 방식을 투 포인터 테크닉이라고 하는데, 투 포인터 테크닉은 정렬된 배열이나 리스트에서 서로 다른 두 개의 원소를 가리키는 두 포인터를 조작하여 원하는 조건을 만족하는 쌍이나 부분 배열을 찾는데 유용하게 사용할 수 있다.

 

이 문제처럼  두 포인터가 두 배열의 시작점에서 시작하여 둘 중 하나의 포인터를 앞으로 이동시키는 방식도 가능하고, 이외에도 두 포인터가 배열의 양 끝에서 시작하여 중앙으로 이동시키는 시나리오도 가능하다.

 

 

int getCommon(int* nums1, int nums1Size, int* nums2, int nums2Size) {
    int i = 0, j = 0;

    while(i < nums1Size && j < nums2Size) {
        if(nums1[i] == nums2[j]) return nums1[i];
        if(nums1[i] < nums2[j]) i++;
        else j++;
    }

    return -1;
}