thảo luận Leetcode mỗi ngày

class Solution {
    public int findLengthOfShortestSubarray(int[] arr) {
        int n = arr.length;
        
        // Find the longest non-decreasing subarray from the start
        int left = 0;
        while (left < n - 1 && arr[left] <= arr[left + 1]) {
            left++;
        }

        // If the entire array is already sorted
        if (left == n - 1) {
            return 0;
        }

        // Find the right boundary where the array starts to decrease
        int right = n - 1;
        int res = right - left;  // Initial result assumes removing the middle portion
        
        // Adjust right and try to find the shortest subarray to remove
        while (right > left && (right == n - 1 || arr[right] <= arr[right + 1])) {
            // Shift left pointer leftward if arr[right] is smaller than arr[left]
            while (right >= 0 && left >= 0 && arr[right] < arr[left]) {
                left--;
            }
            // Update the minimum length of the subarray to remove
            res = Math.min(res, right - left - 1);
            right--;  // Move the right pointer leftward
        }

        return res;
    }
}

class Solution {
public:
    vector<long long> maximumEvenSplit(long long finalSum) {
        if (finalSum % 2 == 1) return {};
        vector<long long> ret;
        for (int i = 2; finalSum >= i; i += 2) {
            ret.push_back(i);
            finalSum -= i;
        }
        ret.back() += finalSum;
        return ret;
    }
};

class Solution {
    boolean[] mono_prefix;
    boolean[] mono_suffix;
    public int findLengthOfShortestSubarray(int[] arr) {
        int n = arr.length;
        int res = 0;
        int l = 0;
        int r = n - 1;
        int[] extended_arr = new int[n+2];
        extended_arr[0]=-1;
        extended_arr[n+1]=1000000001;
        for(int i =0;i<n;i++){
            extended_arr[i+1]=arr[i];
        }
        mono_prefix = new boolean[n+2];
        mono_prefix[0] = true;

        for(int i =1 ; i <= n+1;i++){
            mono_prefix[i]=mono_prefix[i-1] && (extended_arr[i]>=extended_arr[i-1]);
        }
        mono_suffix = new boolean[n+2];
        mono_suffix[n+1] = true;
        for(int i =1 ; i <=n+1;i++){
            mono_suffix[n+1-i] = mono_suffix[n+2-i]&&(extended_arr[n+2-i]>=extended_arr[n+1-i]);
        }
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (condition(mid, extended_arr)) {
                res = mid;
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        return res;
    }

    public boolean condition(int len, int[] arr) {
        int n = arr.length;
        for(int i =0 ; i < n-1-len;i++){
            if(mono_prefix[i] && mono_suffix[i+len+1] && arr[i]<=arr[i+len+1]) return true;
        }
        return false;
    }
}

class Solution {
    public int findLengthOfShortestSubarray(int[] arr) {
        int l = 0, r = arr.length - 1;
        for (; l < arr.length - 1 && arr[l] <= arr[l + 1]; l++);
        for (; r > 0 && arr[r] >= arr[r - 1]; r--);
        int ans = Math.min(arr.length - 1 - l, r);
        for (int i = l, j = arr.length - 1; i >= 0 && j >= r && i < j;) {
            if (arr[i] <= arr[j]) j--;
            else i--;
            ans = Math.min(ans, j - i);
        }
        return ans;
    }
}

class Solution:
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        right_arr = [arr[-1]]
        for num in arr[-2::-1]:
            if num > right_arr[-1]: break
            right_arr.append(num)
       
        if len(right_arr) == len(arr): return 0

        right_arr = right_arr[::-1]
        res = len(right_arr)
       
        for index, num in enumerate(arr):
            if index and arr[index] < arr[index - 1]: break
            remain = len(right_arr) - bisect_left(right_arr, num)
            res = max(res, index + 1 + remain)

        return len(arr) - res

class Solution {
public:
    int connectTwoGroups(vector<vector<int>>& cost) {
        int n = cost.size();
        int m = cost[0].size();
        vector<vector<int>> dp(n, vector<int> (1<<m, 1000000000));
        for (int mask=1; mask<(1<<m); ++mask) {
            int c = 0;
            for (int i=0; i<m; ++i) {
                if (mask & (1<<i)) {
                    c += cost[0][i];
                }
            }
            dp[0][mask] = c;
        }

        for (int i=1; i<n; ++i) {
            for (int mask=1; mask<(1<<m); ++mask) {
                for (int j=0; j<m; ++j) {
                    if (mask & (1<<j)) {
                        dp[i][mask] = min(dp[i][mask], dp[i-1][mask] + cost[i][j]);
                        dp[i][mask] = min(dp[i][mask], min(dp[i-1][mask^(1<<j)], dp[i][mask^(1<<j)]) + cost[i][j]);
                    }
                }
            }
        }

        return dp[n-1][(1<<m)-1];
        
    }
};

class Solution:
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        n = len(arr)
        prefix_sorted = [True] * n
        suffix_sorted = [True] * n

        for i in range(1, n):
            prefix_sorted[i] = prefix_sorted[i - 1] and arr[i - 1] <= arr[i]
            
        for i in range(n - 2, -1, -1):
            suffix_sorted[i] = suffix_sorted[i + 1] and arr[i] <= arr[i + 1]

        def check(k):

            for start in range(n - k + 1):
                end = start + k - 1

                left_sorted = prefix_sorted[start - 1] if start > 0 else True
                right_sorted = suffix_sorted[end + 1] if end + 1 < n else True
                boundary_valid = (arr[start - 1] <= arr[end + 1]) if start > 0 and end + 1 < n else True

                if left_sorted and right_sorted and boundary_valid:
                    return True

            return False

        left = 0
        right = n
        while left < right:
            mid = (left + right) // 2
            if check(mid):
                right = mid
            else:
                left = mid + 1
            
        return right

class Solution {
    public List<Long> maximumEvenSplit(long finalSum) {
        List<Long> res = new ArrayList<>();
        Long sum = 0L;
        if (finalSum % 2 == 1)
        {
            return res;
        }
        for (int i = 2; sum < finalSum; i += 2)
        {
            if(sum + i == finalSum)
            {
                res.add((long)i);
                return res;
            } else
            {
                res.add((long)i);
                sum += i;
            }
        }
        int t = (int)(sum - finalSum)/2;
        res.remove(res.get(t-1));
        return res;
    }
}