문제 링크

내 코드

길이가 짧아 brute force 다 가능할 듯.

• 3ms, 32.8MB

class Solution {
public:
    vector<int> resultsArray(vector<int>& nums, int k) {
        int n = static_cast<int>(nums.size());
        vector<int> answer(n - k + 1, -1);

        // nums.length <= 500 => 다 확인해도 되지 않나?
        for(int i{};i<n - k + 1;++i) {
            bool chk{};
            for(int j{i};j < i + k - 1;++j) {
                if(nums[j] + 1 != nums[j + 1]) {
                    chk = true;
                    break;
                }
            }
            if(!chk) {
                answer[i] = nums[i + k - 1];
            }
        }

        return answer;
    }
};

Solution

Approach 1: Brute Force

• 3ms, 32.95MB
• Complexity
  • Let $n$ be the length of the input array nums and $k$ be the length of the subarrays we are checking.
  • Time Complexity: $O(n \cdot k)$
  • Space Complexity: $O(1)$

class Solution {
public:
    vector<int> resultsArray(vector<int>& nums, int k) {
        int length = nums.size();
        vector<int> result(length - k + 1);

        for (int start = 0; start <= length - k; start++) {
            bool isConsecutiveAndSorted = true;

            // Check if the current subarray is sorted and consecutive
            for (int index = start; index < start + k - 1; index++) {
                if (nums[index + 1] != nums[index] + 1) {
                    isConsecutiveAndSorted = false;
                    break;
                }
            }

            // If valid, take the maximum of the subarray, otherwise set to -1
            if (isConsecutiveAndSorted) {
                // Maximum element of this subarray
                result[start] = nums[start + k - 1];
            } else {
                result[start] = -1;
            }
        }

        return result;
    }
};

Approach 2: Sliding Window with Deque

deque를 통한 크기 k인 윈도우 유지

• 새로 삽입된 원소가 연속된 성질을 만족 못 할 경우 window reset (clear)

• window 크기가 k 도달 시 답이 있다면 마지막 값을 없다면 -1로 값 채우기.

• 2ms, 34.16MB

• Complexity

  • Let $n$ be the length of the input array nums and $k$ be the length of the subarrays we are checking.
  • Time Complexity: $O(n)$
  • Space Complexity: $O(k)$

class Solution {
public:
    vector<int> resultsArray(vector<int>& nums, int k) {
        int length = nums.size();
        vector<int> result(length - k + 1, -1);
        deque<int> indexDeque;

        for (int currentIndex = 0; currentIndex < length; currentIndex++) {

            if (!indexDeque.empty() &&
                indexDeque.front() < currentIndex - k + 1) {
                indexDeque.pop_front();
            }

            if (!indexDeque.empty() &&
                nums[currentIndex] != nums[currentIndex - 1] + 1) {
                indexDeque.clear(); // not invalid value
            }

            indexDeque.push_back(currentIndex);

            if (currentIndex >= k - 1) {
                if (indexDeque.size() == k) {
                    result[currentIndex - k + 1] = nums[indexDeque.back()];
                } else {
                    result[currentIndex - k + 1] = -1;
                }
            }
        }

        return result;
    }
};

Approach 3: Optimized Via Counter

deque를 연속된 시퀀스의 길이를 추적하는 counter로 사용 가능. (굳이 모든 원소를 다 갖고 있을 필요가 없기 때문에)

• 카운터가 k 도달 시 유효한 배열, 아닌 경우 -1 저장

• 0ms, 32.84MB
• Complexity
  • Let $n$ be the length of the input array nums and $k$ be the length of the subarrays we are checking.
  • Time Complexity: $O(n)$
  • Space Complexity: $O(1)$

class Solution {
public:
    vector<int> resultsArray(vector<int>& nums, int k) {
        if (k == 1) {
            return nums;  // If k is 1, every single element is a valid subarray
        }

        size_t length = nums.size();
        vector<int> result(length - k + 1, -1);  // Initialize results with -1
        int consecutiveCount = 1;  // Count of consecutive elements

        for (size_t index = 0; index < length - 1; index++) {
            if (nums[index] + 1 == nums[index + 1]) {
                consecutiveCount++;
            } else {
                consecutiveCount = 1;  // Reset count if not consecutive
            }

            // If we have enough consecutive elements, update the result
            if (consecutiveCount >= k) {
                result[index - k + 2] = nums[index + 1];
            }
        }

        return result;
    }
};