p "==========Insert at index=========="

def insert_at_index(arr, size_of_array, index, element)
  arr.insert(index, element)
end

p insert_at_index([1,2,3,4,5,6], 6, 3, 80)

p "==========Array leaders=========="

# https://[Log in to view URL]

def leaders(arr)
    leaders = [arr[-1]]
    max_from_right = arr[-1]

    (arr.length-2).downto(0) do |i|
        if arr[i] >= max_from_right
            max_from_right = arr[i]
            leaders.unshift(arr[i])
        end
    end

    leaders
end

p leaders([10,4,2,4,1])
p leaders([16,17,4,3,5,2])
p leaders([5, 10, 20, 40])

# Similar question in leetcode

# https://[Log in to view URL]

def replace_elements(arr)
  max_from_right = -1  # The last element should always be replaced with -1

  (arr.length - 1).downto(0) do |i|
    new_max = [arr[i], max_from_right].max  # Find the new max before replacing
    arr[i], max_from_right = max_from_right, new_max  # Replace and update max
  end

  arr
end

p replace_elements([17, 18, 5, 4, 6, 1])

def greater_elements(arr)
    i = arr.length - 1
    max_from_right = -1
    while i >= 0 do
        new_max = [arr[i], max_from_right].max
        arr[i] = max_from_right
        max_from_right = new_max
        i -= 1
    end
    arr
end

p greater_elements([17, 18, 5, 4, 6, 1])

p "==========Flatten an array=========="

def flatter(arr)
  arr.each_with_object([]){|element, obj| obj.push *(element.is_a?(Array) ? flatter(element) : element)}
end

p flatter([1, 2, 3, [4, 4, 49, [8, 6, 4, 2, 7]]])

def flattify(arr, flattened)
    arr.each do |element|
        if element.class == Array
            flattify(element, flattened)
        else
            flattened.push element
        end
    end
    flattened
end

p flattify([1, 2, 3, [4, 4, 49, [8, 6, 4, 2, 7]]], [])

p "==========Mirror inverse array ?=========="

# https://[Log in to view URL]

def is_mirrored?(arr)
  n = arr.length-1
  for i in 0...n
    return false if arr[arr[i]] != i
  end
  true
end

p is_mirrored?([3, 4, 2, 0, 1])

p is_mirrored?([1, 2, 3, 0])

p "==========Maximum Index=========="

def max_index_diff(arr, n)
  max_diff = 0
  i = 0
  j = 0

  l_min = Array.new(n)
  r_max = Array.new(n)

  l_min[0] = arr[0]
  (1...n).each do |i|
    l_min[i] = [arr[i], l_min[i - 1]].min
  end

  r_max[n - 1] = arr[n - 1]
  (n - 2).downto(0) do |j|
    r_max[j] = [arr[j], r_max[j + 1]].max
  end

  i = 0
  j = 0
  max_diff = -1
  while j < n && i < n
    if l_min[i] <= r_max[j]
      max_diff = [max_diff, j - i].max
      j += 1
    else
      i += 1
    end
  end

  max_diff
end


# max_arr = [1, 10]
max_arr = [9, 2, 3, 4, 5, 6, 7, 8, 18, 0]

p max_index_diff(max_arr, max_arr.length)


p "==========Search in rotated sorted array=========="

# https://[Log in to view URL]

def search_rotated_array(nums, target)
    low = 0
    high = nums.length - 1
    
    while low <= high
      mid = (low + high) / 2
    
      if nums[mid] == target
        return mid
      elsif nums[low] <= nums[mid]
        if target >= nums[low] && target < nums[mid]
          high = mid - 1
        else
          low = mid + 1
        end
      else
        if target > nums[mid] && target <= nums[high]
          low = mid + 1
        else
          high = mid - 1
        end
      end
    end
    
    return -1
end

p search_rotated_array([5, 6, 7, 8, 9, 10, 1, 2, 3], 2)