Untitled

def activityNotifications(expenditure, d)
    return 0 if expenditure.size <= d

    notifications_count = 0
    
    # 201 because the expenditures range from 0 to 200.
    frequencies = Array.new(201, 0)

    # fill frequencies array 
    expenditure[0, d].each do |exp|
        frequencies[exp] += 1
    end

    # find median index
    median_position = d / 2 + 1
    
    # use median index shift for odd arrays
    shift = d % 2 == 0 ? 1 : 0

    expenditure.each_with_index do |exp, idx|
        # ignore first d expenditures because of data collecting
        next if idx < d

        median_value = calculate_median_sum(frequencies, median_position, shift)
        
        notifications_count += 1 if exp >= median_value

        # 'shift' expenditure window by 1
        frequencies[expenditure[idx - d]] -= 1
        frequencies[exp] += 1
    end

    notifications_count
end

def calculate_median_sum(frequencies, median_position, shift)
    frequencies_sum = 0
    median_value = 0

    # d = 3
    # [1 3 3 2]

     # median_position = 2
     # frequencies = [0 1 1 2 0 0... 0]
     # shift = 0
    frequencies.each_with_index do |freq, exp|
        frequencies_sum += freq
        
        # check a position where should be the median
        if median_value == 0 && frequencies_sum >= median_position - shift
            median_value += exp
        end
        
        # end of median_value increasing
        if frequencies_sum >= median_position
            median_value += exp
            break
        end
    end

    median_value
end