Largest Subarray Length K

🏠 ⬅️ ➡️

An array A is larger than some array B if for the first index i where A[i] != B[i], A[i] > B[i].

For example, consider 0-indexing:

  • [1,3,2,4] > [1,2,2,4], since at index 1, 3 > 2.
  • [1,4,4,4] < [2,1,1,1], since at index 0, 1 < 2.

A subarray is a contiguous subsequence of the array.

Given an integer array nums of distinct integers, return the largest subarray of nums of length k.

Example 1:

Input: nums = [1,4,5,2,3], k = 3 Output: [5,2,3] Explanation: The subarrays of size 3 are: [1,4,5], [4,5,2], and [5,2,3]. Of these, [5,2,3] is the largest.

Example 2:

Input: nums = [1,4,5,2,3], k = 4 Output: [4,5,2,3] Explanation: The subarrays of size 4 are: [1,4,5,2], and [4,5,2,3]. Of these, [4,5,2,3] is the largest.

Example 3:

Input: nums = [1,4,5,2,3], k = 1 Output: [5]

Constraints:

  • 1 <= k <= nums.length <= 105
  • 1 <= nums[i] <= 109
  • All the integers of nums are unique.

Follow up: What if the integers in nums are not distinct?

Note: This problem is from LeetCode.
❌ Compiled
❌ Executed
❌ Correct 
program main
    implicit none

    integer, parameter :: n = 5
    integer, dimension(n) :: A, B

    A = [1, 3, 2, 4]
    B = [1, 2, 2, 4]
    print '(L1)', larger_than(A, B)

    A = [1, 4, 5, 2, 3]
    B = [2, 1, 1, 1]
    print '(L1)', larger_than(A, B)

contains

    logical function larger_than(A, B) result(larger)
        implicit none
        integer, intent(in) :: A(:), B(:)
        integer :: i

        do i = 1, size(A)
            if (A(i) /= B(i)) then
                larger = A(i) > B(i)
                exit
            end if
        end do
    end function larger_than

end program main
❌ Compiled
❌ Executed
❌ Correct 
module largest_subarray
implicit none
contains
function largest_subarray(nums, k) result(largest)
integer, intent(in) :: nums(:), k
integer :: largest(size(nums))
integer :: i, j, max_size, max_val
max_size = 0
max_val = 0
do i = 1, size(nums) - k + 1
    do j = i, i + k - 1
        if (nums(j) > max_val) then
            max_val = nums(j)
            max_size = j - i + 1
        end if
    end do
end do
largest = nums(i:i + max_size - 1)
end function
end module

program test_largest_subarray
use largest_subarray
implicit none
integer :: nums(5)
nums = [1, 4, 5, 2, 3]
write (*, '(A, I0)') 'Largest subarray of length 3: ', largest_subarray(nums, 3)
nums = [1, 4, 5, 2, 3]
write (*, '(A, I0)') 'Largest subarray of length 4: ', largest_subarray(nums, 4)
nums = [1, 4, 5, 2, 3]
write (*, '(A, I0)') 'Largest subarray of length 1: ', largest_subarray(nums, 1)
end program
🌐 Data from online sources 
class ParkingSystem:

    def __init__(self, big: int, medium: int, small: int):
        self.slots = [big, medium, small]

    def addCar(self, carType: int) -> bool:
        if self.slots[carType - 1] > 0:
            self.slots[carType - 1] -= 1
            return True
        else:
            return False

The ParkingSystem class is designed such that an instance of the class contains an array of integers 'slots', representing the number of big, medium, and small slots available. The constructor takes in the respective number of big, medium, and small slots as arguments and assigns the input values to the slots array.

The addCar() function is then implemented to take in an integer value carType (1, 2, or 3) representing the type of car. We then check if the number of slots for that specific type of car is more than 0. If there is available space (i.e., the respective slot count is > 0), we decrement the slot count and return true. If there is no space available (i.e., slot count is 0), we return false.

The solution is O(1) for addCar() as it directly accesses and modifies the slots array.

🌐 Data from online sources 
class ParkingSystem {
public:
    ParkingSystem(int big, int medium, int small) {
        slots = {big, medium, small};
    }

    bool addCar(int carType) {
        if (slots[carType - 1] > 0) {
            slots[carType - 1]--;
            return true;
        } else {
            return false;
        }
    }

private:
    vector<int> slots;
};

The ParkingSystem class is designed such that an instance of the class contains an array of integers 'slots', representing the number of big, medium, and small slots available. The constructor takes in the respective number of big, medium, and small slots as arguments and assigns the input values to the slots array.

The addCar() function is then implemented to take in an integer value carType (1, 2, or 3) representing the type of car. We then check if the number of slots for that specific type of car is more than 0. If there is available space (i.e., the respective slot count is > 0), we decrement the slot count and return true. If there is no space available (i.e., slot count is 0), we return false.

The solution is O(1) for addCar() as it directly accesses and modifies the slots array.