Check if an Array Is Consecutive

šŸ  ā¬…ļø āž”ļø

Given an integer array nums, return true if nums is consecutive, otherwise return false.

An array is consecutive if it contains every number in the range [x, x + n - 1] (inclusive), where x is the minimum number in the array and n is the length of the array.

Example 1:

Input: nums = [1,3,4,2] Output: true Explanation: The minimum value is 1 and the length of nums is 4. All of the values in the range [x, x + n - 1] = [1, 1 + 4 - 1] = [1, 4] = (1, 2, 3, 4) occur in nums. Therefore, nums is consecutive.

Example 2:

Input: nums = [1,3] Output: false Explanation: The minimum value is 1 and the length of nums is 2. The value 2 in the range [x, x + n - 1] = [1, 1 + 2 - 1], = [1, 2] = (1, 2) does not occur in nums. Therefore, nums is not consecutive.

Example 3:

Input: nums = [3,5,4] Output: true Explanation: The minimum value is 3 and the length of nums is 3. All of the values in the range [x, x + n - 1] = [3, 3 + 3 - 1] = [3, 5] = (3, 4, 5) occur in nums. Therefore, nums is consecutive.

Constraints:

  • 1 <= nums.length <= 105
  • 0 <= nums[i] <= 105
Note: This problem is from LeetCode.
āŒ Compiled
āŒ Executed
āŒ Correct 
program main
    implicit none

    integer, parameter :: n = 4
    integer, dimension(n) :: nums
    logical :: result

    ! Example 1
    nums = [1, 3, 4, 2]
    result = is_consecutive(nums)
    write (*, '(A, L1)') 'Example 1: ', result

    ! Example 2
    nums = [1, 3]
    result = is_consecutive(nums)
    write (*, '(A, L1)') 'Example 2: ', result

    ! Example 3
    nums = [3, 5, 4]
    result = is_consecutive(nums)
    write (*, '(A, L1)') 'Example 3: ', result

contains

    function is_consecutive(nums) result(result)
        implicit none
        integer, dimension(:), intent(in) :: nums
        logical :: result
        integer :: x, n

        x = minval(nums)
        n = size(nums)

        result = all([x, x + n - 1] == nums)
    end function is_consecutive
end program main
āŒ Compiled
āŒ Executed
āŒ Correct 
module is_consecutive

implicit none

contains

function is_consecutive(nums) result(is_consecutive)

integer, intent(in) :: nums(:)
logical :: is_consecutive

! Variables
integer :: x, n, i

! Initialize variables
x = minval(nums)
n = size(nums)
is_consecutive = .true.

! Check if all values in the range [x, x + n - 1] occur in nums
do i = x, x + n - 1
    if (.not. any(nums == i)) then
        is_consecutive = .false.
        exit
    end if
end do

end function is_consecutive

end module is_consecutive

program test_is_consecutive

use is_consecutive, only : is_consecutive
implicit none

! Test case 1:
print *, is_consecutive([1, 3, 4, 2])
! Expected output:
! .true.

! Test case 2:
print *, is_consecutive([1, 3])
! Expected output:
! .false.

! Test case 3:
print *, is_consecutive([3, 5, 4])
! Expected output:
! .true.

end program test_is_consecutive
šŸŒ Data from online sources 
from bisect import bisect_left

def maxFruits(fruits, startPos, k):
    n = len(fruits)
    left, right = [0] * (n + 1), [0] * (n + 1)
    j = 0

    for i in range(n):
        while j < n and fruits[j][0] - fruits[i][0] <= k:
            right[i + 1] += fruits[j][1]
            j += 1
        right[i + 1] += right[i]
        if j < n and fruits[j][0] - startPos <= k:
            right[0] += fruits[j][1]
            j += 1

    j = n - 1
    for i in range(n - 1, -1, -1):
        while j >= 0 and fruits[j][0] - fruits[i][0] <= k:
            left[i] += fruits[j][1]
            j -= 1
        left[i] += left[i + 1]

    ans = 0
    for i in range(n):
        rest = max(0, k - abs(fruits[i][0] - startPos))
        idx = bisect_left(fruits, [fruits[i][0] + rest, 0])
        ans = max(ans, left[i] + right[idx])

    return ans

1. Create left and right arrays of size n+1 filled with zeros, to store the cumulative fruits at each position.
  1. Initialize a cursor j with value 0.
  2. Iterate the fruits array and populate the right array with total fruits in the range of k units.
  3. Then populate the left array with the remaining fruits by iterating the array in reverse order.
  4. Initialize an answer variable, ans, to 0.
  5. Iterate the fruits array again, calculating the remaining steps after reaching a position and using a binary search technique (in each language) to find the index of the next fruit that can be reached. Update ans with the maximum sum of fruit harvest.
  6. Finally, return ans as the solution.
šŸŒ Data from online sources 
#include <vector>
#include <algorithm>
using namespace std;

int maxFruits(vector<vector<int>>& fruits, int startPos, int k) {
    int n = fruits.size();
    vector<int> left(n + 1, 0), right(n + 1, 0);
    int j = 0;

    for (int i = 0; i < n; i++) {
        while (j < n && fruits[j][0] - fruits[i][0] <= k) {
            right[i + 1] += fruits[j][1];
            j++;
        }
        right[i + 1] += right[i];
        if (j < n && fruits[j][0] - startPos <= k) {
            right[0] += fruits[j][1];
            j++;
        }
    }

    j = n - 1;
    for (int i = n - 1; i >= 0; i--) {
        while (j >= 0 && fruits[j][0] - fruits[i][0] <= k) {
            left[i] += fruits[j][1];
            j--;
        }
        left[i] += left[i + 1];
    }

    int ans = 0;
    for (int i = 0; i < n; i++) {
        int rest = max(0, k - abs(fruits[i][0] - startPos));
        int idx = upper_bound(fruits.begin(), fruits.end(), vector<int>{fruits[i][0] + rest, 0}) - fruits.begin();
        ans = max(ans, left[i] + right[idx]);
    }
    return ans;
}

1. Create left and right arrays of size n+1 filled with zeros, to store the cumulative fruits at each position.
  1. Initialize a cursor j with value 0.
  2. Iterate the fruits array and populate the right array with total fruits in the range of k units.
  3. Then populate the left array with the remaining fruits by iterating the array in reverse order.
  4. Initialize an answer variable, ans, to 0.
  5. Iterate the fruits array again, calculating the remaining steps after reaching a position and using a binary search technique (in each language) to find the index of the next fruit that can be reached. Update ans with the maximum sum of fruit harvest.
  6. Finally, return ans as the solution.