915. Partition Array into Disjoint Intervals

leetcode

#array#csharp#graph#intervals#leetcode#math#two-pointers

Task

: medium

Задав целочисленный массив nums, разбейте его на два (смежных) подмассива left и right так, чтобы: каждый элемент left был меньше или равен каждому элементу right. left и right были непустыми. left имел наименьший возможный размер. Верните длину left после такого разбиения. Тестовые примеры генерируются такие, что разбиение существует.

Пример:

Input: nums = [5,0,3,8,6]

Output: 3

C# solution

matched/original

public class Solution {
    public int PartitionDisjoint(int[] nums) {
        int n = nums.Length;
        int[] maxLeft = new int[n];
        int[] minRight = new int[n];
        
        maxLeft[0] = nums[0];
        for (int i = 1; i < n; i++) {
            maxLeft[i] = Math.Max(maxLeft[i - 1], nums[i]);
        }
        
        minRight[n - 1] = nums[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            minRight[i] = Math.Min(minRight[i + 1], nums[i]);
        }
        
        for (int i = 0; i < n - 1; i++) {
            if (maxLeft[i] <= minRight[i + 1]) {
                return i + 1;
            }
        }
        return n;
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int PartitionDisjoint(vector<int>& nums) {
        int n = nums.size();
        vector<int>& maxLeft = new int[n];
        vector<int>& minRight = new int[n];
        
        maxLeft[0] = nums[0];
        for (int i = 1; i < n; i++) {
            maxLeft[i] = max(maxLeft[i - 1], nums[i]);
        }
        
        minRight[n - 1] = nums[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            minRight[i] = min(minRight[i + 1], nums[i]);
        }
        
        for (int i = 0; i < n - 1; i++) {
            if (maxLeft[i] <= minRight[i + 1]) {
                return i + 1;
            }
        }
        return n;
    }
}

Java solution

auto-draft, review before submit

import java.util.*;
import java.math.*;

// Auto-generated Java draft from the C# solution. Review API differences before LeetCode submit.
public class Solution {
    public int PartitionDisjoint(int[] nums) {
        int n = nums.length;
        int[] maxLeft = new int[n];
        int[] minRight = new int[n];
        
        maxLeft[0] = nums[0];
        for (int i = 1; i < n; i++) {
            maxLeft[i] = Math.max(maxLeft[i - 1], nums[i]);
        }
        
        minRight[n - 1] = nums[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            minRight[i] = Math.min(minRight[i + 1], nums[i]);
        }
        
        for (int i = 0; i < n - 1; i++) {
            if (maxLeft[i] <= minRight[i + 1]) {
                return i + 1;
            }
        }
        return n;
    }
}

Python solution

matched/original

class Solution {
    func partitionDisjoint(_ nums: [Int]) -> Int {
        let n = nums.count
        var maxLeft = [Int](repeating: 0, count: n)
        var minRight = [Int](repeating: 0, count: n)
        
        maxLeft[0] = nums[0]
        for i in 1..<n {
            maxLeft[i] = max(maxLeft[i - 1], nums[i])
        }
        
        minRight[n - 1] = nums[n - 1]
        for i in stride(from: n - 2, through: 0, by: -1) {
            minRight[i] = min(minRight[i + 1], nums[i])
        }
        
        for i in 0..<n - 1 {
            if maxLeft[i] <= minRight[i + 1] {
                return i + 1
            }
        }
        return n
    }
}

Explanation

Algorithm

Создать массив max_left и min_right.

Заполнить max_left максимальными значениями от начала массива до текущего индекса.

Заполнить min_right минимальными значениями от текущего индекса до конца массива.

Найти индекс, где max_left[i] меньше или равен min_right[i + 1].

Вернуть длину левого подмассива.

😎