[LeetCode] 3152. Special Array II

 

3151. Special Array II

 

❓Problem

An array is considered special if every pair of its adjacent elements contains two numbers with different parity.

You are given an array of integer nums and a 2D integer matrix queries, where for queries[i] = [fromi, toi] your task is to check that 
subarray
 nums[fromi..toi] is special or not.

Return an array of booleans answer such that answer[i] is true if nums[fromi..toi] is special.

 

Example 1:

Input: nums = [3,4,1,2,6], queries = [[0,4]]

Output: [false]

Explanation:

The subarray is [3,4,1,2,6]. 2 and 6 are both even.

Example 2:

Input: nums = [4,3,1,6], queries = [[0,2],[2,3]]

Output: [false,true]

Explanation:

The subarray is [4,3,1]. 3 and 1 are both odd. So the answer to this query is false.
The subarray is [1,6]. There is only one pair: (1,6) and it contains numbers with different parity. So the answer to this query is true.

 

 

🗝️ 최초 Answer

/**
 * @param {number[]} nums
 * @param {number[][]} queries
 * @return {boolean[]}
 */
var isArraySpecial = function(nums, queries) {
    let parity = [];
    let result = [];

    for (let i = 1 ; i <nums.length ; i++ ){
        if((nums[i] % 2) == nums[i-1] % 2) parity.push(true);
        else parity.push(false);
    }

    for(let i = 0 ; i < queries.length ; i++){
        let subset = parity.slice(queries[i][0], queries[i][1])
        if(subset.includes(true)) result.push(false);
        else result.push(true);
    }

    return result;
};

 

🗝️ 최종 Answer

/**
 * @param {number[]} nums
 * @param {number[][]} queries
 * @return {boolean[]}
 */
var isArraySpecial = function(nums, queries) {
    const fails = []
    let res = []
    
    for (let i = 0; i < nums.length - 1; i++) {
        const first = (nums[i] % 2)
        const second = nums[i + 1] % 2
        if (first === second) fails.push(i)
    }
    
    for (const [from, to] of queries) {
        if (from === to) {
            res.push(true)
            continue
        }
        let index1 = binarySearch(fails, from)
        let index2 = binarySearch(fails, to)
        
        if (index1 !== index2) res.push(false)
        else res.push(true)
    }
    
    return res
};

let binarySearch = (arr, target) => {
    let left = 0;
    let right = arr.length;
    while (left < right) {
        let mid = Math.floor((left + right) / 2);
        if (arr[mid] >= target) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }

    return left;
}

 

🎈Review

• 최초 답처럼 풀면 간단한 배열은 풀림 하지만 데이터가 늘어라면 TIME LIMIT EXCEEDED
• 결론은 이진 탐색을 이용하여 풀어야 한다. 이진 탐색에 대해서는 아래와 같이 정리해보자.

 

🎀 이진 탐색 (Binary Search)

• 이진 탐색은 정렬된 배열에서 원하는 값을 효율적으로 찾는 알고리즘
• 시간 복잡도: O(logn)

1. 초기화
시작 인덱스, left = 0
끝 인덱스, right = 배열의 마지막 index

2. 반복
중간 index, mid = left + Math.floor((right - left) / 2)
- 만약 중간 값이 찾고자 하는 값과 같다면, 해당 인덱스 반환
- 만약 중간 값이 크다면, 오른쪽 절반은 버리고 right = mid -1 로 업데이트
- 만약 중간 값이 작다면, 왼쪽을 버리고 left = mid + + 1 로 업데이트

3. 종료
없다면 -1 반환