Find Mountain Numbers with Min Sum in a List

Given an array of integers, find three number at indices i, j, k such that a[j] is greater than a[i] and a[k] and i < j < k. We do not need to return the indices or the numbers, ,but just the sum. If more than one triplets of number exist, return the min sum. If none exists, return -1. This is a problem from leetcode at this link .

Solution: Naiive Solution, But only works if consecutive

class Solution: def minimumSum(self, nums: List[int]) -> int: diff_arr = [] N = len(nums) # find diff array for i in range(1,N): diff_arr.append(nums[i]-nums[i-1]) # find mountain here # mountain is characterized by +ve number in diff_arr followed by a -ve number mountain_list = [] for idx,i in enumerate(diff_arr[:-1]): if i>0 and diff_arr[idx+1]<0: mountain_list.append(idx) if len(mountain_list): print(mountain_list) ret_sum = 9999999999 for i in mountain_list: summ = sum(nums[i:i+3]) print(f"For mountain {nums[i:i+3]}, sum is {summ}") if summ < ret_sum: ret_sum = summ else: return -1 return ret_sum

The above solution works if we are only considering the result to include consecutive numbers. For the case like, [5,4,8,7,10,2], this does not work because the min sum mountain is 4, 7, 2 which are not consecutive numbers. We should run some kind of pointers here to find the best solution to handle case of non-consecutives.

Solution: For Non Consecutive

class Solution: def minimumSum(self, nums: List[int]) -> int: N = len(nums) return_val = float("inf") found_one = False for idx, i in enumerate(nums): if idx==0: continue left_pointer = idx-1 right_pointer = idx+1 # let us find numbers smaller than i in either direction of i l_mountain = False l_val = i while(left_pointer >= 0): if nums[left_pointer] < i and nums[left_pointer] < l_val: l_mountain = True l_val = nums[left_pointer] left_pointer -= 1 if not l_mountain: continue r_mountain = False r_val = i while(right_pointer < N): if nums[right_pointer] < i and nums[right_pointer] < r_val: r_mountain = True r_val = nums[right_pointer] right_pointer += 1 if r_mountain and l_mountain: found_one = True summ = i + r_val + l_val if summ < return_val: return_val = summ return return_val if found_one else -1

The above solution works, but it is highly unoptimized. What we do here is, we consider every iteration as the peak of the mountain. Thus, for each, if we are able to find min on each side, if they exist, we can compute the sum of the mountain. If min does not exist on any one of the sides, then mountain does not exist.

Solution: Optimized Solution

class Solution: def minimumSum(self, nums: List[int]) -> int: N = len(nums) ret_val = float('inf') # we will create two lists, l_list and r_list # l_list will hold min value to the left of each item in nums l_list = [float('inf')]*N r_list = [float('inf')]*N for i in range(1,N): l_list[i] = min(l_list[i-1],nums[i-1]) for i in range(N-2,0,-1): r_list[i] = min(r_list[i+1],nums[i+1]) # now let us compute the mountain and sum found = False for i in range(0,N-1): if nums[i]>l_list[i] and nums[i]>r_list[i]: found = True summ = nums[i] + l_list[i] + r_list[i] if summ < ret_val: ret_val = summ if found: return ret_val else: return -1

In the above solution, we create 2 lists of min values on either side of each each index. And, at the end we run yet another loop for test the mountain condition and find our answer.