Smallest Range I

🏠 ⬅️ ➡️

You are given an integer array nums and an integer k.

In one operation, you can choose any index i where 0 <= i < nums.length and change nums[i] to nums[i] + x where x is an integer from the range [-k, k]. You can apply this operation at most once for each index i.

The score of nums is the difference between the maximum and minimum elements in nums.

Return the minimum score of nums after applying the mentioned operation at most once for each index in it.

Example 1:

Input: nums = [1], k = 0 Output: 0 Explanation: The score is max(nums) - min(nums) = 1 - 1 = 0.

Example 2:

Input: nums = [0,10], k = 2 Output: 6 Explanation: Change nums to be [2, 8]. The score is max(nums) - min(nums) = 8 - 2 = 6.

Example 3:

Input: nums = [1,3,6], k = 3 Output: 0 Explanation: Change nums to be [4, 4, 4]. The score is max(nums) - min(nums) = 4 - 4 = 0.

Constraints:

  • 1 <= nums.length <= 104
  • 0 <= nums[i] <= 104
  • 0 <= k <= 104
Note: This problem is from LeetCode.
❌ Compiled
❌ Executed
❌ Correct 
program main
    implicit none

    integer, parameter :: n = 1
    integer, parameter :: k = 0
    integer, dimension(n) :: nums
    integer :: i, j, x
    integer :: score

    ! Example 1
    nums = [1]
    write (*, '(A)') 'Example 1:'
    write (*, '(A)') 'Input: nums = [1], k = 0'
    write (*, '(A)') 'Output:', solve(nums, k)
    write (*, '(A)') 'Expected: 0'
    write (*, *)

    ! Example 2
    nums = [0, 10]
    write (*, '(A)') 'Example 2:'
    write (*, '(A)') 'Input: nums = [0, 10], k = 2'
    write (*, '(A)') 'Output:', solve(nums, k)
    write (*, '(A)') 'Expected: 6'
    write (*, *)

    ! Example 3
    nums = [1, 3, 6]
    write (*, '(A)') 'Example 3:'
    write (*, '(A)') 'Input: nums = [1, 3, 6], k = 3'
    write (*, '(A)') 'Output:', solve(nums, k)
    write (*, '(A)') 'Expected: 0'
    write (*, *)

contains

    function solve(nums, k) result(min_score)
        implicit none
        integer, intent(in) :: nums(:), k
        integer :: min_score
        integer :: i, j, x

        do i = 1, size(nums)
            do j = 1, size(nums)
                if (i /= j) then
                    x = nums(j) + k
                    if (x >= 0 .and. x <= 100) then
                        nums(j) = x
                    end if
                end if
            end do
        end do

        min_score = maxval(nums) - minval(nums)

    end function solve

end program main
❌ Compiled
❌ Executed
❌ Correct 
module MinimumScoreTrips
    implicit none
    private
    public :: minimumScoreTrips
contains
    function minimumScoreTrips(nums, k) result(min_score)
        integer, intent(in) :: nums(:)
        integer, intent(in) :: k
        integer :: min_score
        integer :: max_val, min_val
        integer :: i

        ! Find the maximum and minimum values in the array
        max_val = maxval(nums)
        min_val = minval(nums)

        ! Initialize the minimum score to the difference between the maximum and minimum values
        min_score = max_val - min_val

        ! Loop through each index in the array
        do i = 1, size(nums)
            ! Check if the value at the current index is within the range of k
            if (abs(nums(i)) <= k) then
                ! If it is, then calculate the new maximum and minimum values
                max_val = max(max_val, nums(i) + k)
                min_val = min(min_val, nums(i) - k)

                ! Calculate the new score
                min_score = min(min_score, max_val - min_val)
            end if
        end do
    end function minimumScoreTrips
end module MinimumScoreTrips

! Test the function with the given examples
program test_minimum_score_trips
    use MinimumScoreTrips
    implicit none
    integer, parameter :: nums1(1) = [1]
    integer, parameter :: nums2(2) = [0, 10]
    integer, parameter :: nums3(3) = [1, 3, 6]
    integer, parameter :: k1 = 0
    integer, parameter :: k2 = 2
    integer, parameter :: k3 = 3
    integer :: min_score

    ! Test case 1:
    min_score = minimumScoreTrips(nums1, k1)
    write (*,*) "Test case 1:", min_score

    ! Test case 2:
    min_score = minimumScoreTrips(nums2, k2)
    write (*,*) "Test case 2:", min_score

    ! Test case 3:
    min_score = minimumScoreTrips(nums3, k3)
    write (*,*) "Test case 3:", min_score
end program test_minimum_score_trips
🌐 Data from online sources 
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def middleNode(head):
    slow = head
    fast = head

    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

    return slow

The algorithm uses the tortoise and hare algorithm (slow and fast pointers). The slow pointer moves one step at a time, while the fast pointer moves two steps at a time. Since the fast pointer is moving twice as fast as the slow pointer, when the fast pointer reaches the end of the list, the slow pointer will be in the middle. Thus, we can just return the slow pointer as the middle node. If there are two middle nodes, the slow pointer will be on the second middle node, as specified in the problem statement.

🌐 Data from online sources 
class ListNode {
public:
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(NULL) {}
};

ListNode* middleNode(ListNode* head) {
    ListNode* slow = head;
    ListNode* fast = head;

    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
    }

    return slow;
}

The algorithm uses the tortoise and hare algorithm (slow and fast pointers). The slow pointer moves one step at a time, while the fast pointer moves two steps at a time. Since the fast pointer is moving twice as fast as the slow pointer, when the fast pointer reaches the end of the list, the slow pointer will be in the middle. Thus, we can just return the slow pointer as the middle node. If there are two middle nodes, the slow pointer will be on the second middle node, as specified in the problem statement.