Hello everyone. The reason for this blog is that I haven't seen much talk about solutions to this type of problem here, so I'd like to provide a basic introduction of it to this community.

Let's first look at the naive solution to this problem.

The naive solution to this problem for an array-like data structure $$$A$$$ is, for each element $$$A_i$$$, iterate through the entire data structure, and if you find an element $$$A_j$$$ satisfying $$$A_j < A_i$$$, move onto the next element $$$A_{i + 1}$$$. If you don't, you have your answer, $$$A_i$$$.

This is how one might implement such a solution in python:

def find_minimum(A):
	for i in range(len(A)):
		for j in range(len(A)):
			if A[j] < A[i]:
				break
		else:
			return A[i]

Unfortunately, this works in $$$O(n^2)$$$ time. How can we optimize this? We can use dynamic programming.

For a $$$1$$$-indexed array-like data structure $$$A$$$ of length $$$n$$$, let's define $$$dp_i$$$ as the minimum element that appears in the substructure $$$A[i...n]$$$.

It is clear that the minimum element that appears in $$$A[n...n]$$$ is simply $$$A_n$$$. Therefore, our base case is $$$dp_{n} = A_n$$$. For indices $$$1...n - 1$$$, we can construct our answer using this recurrence relation: $$$dp_i = min(A_i, dp_{i + 1})$$$. It is clear that the answer to our problem is $$$dp_1$$$.

This works in $$$O(n)$$$ time and $$$O(n)$$$ space. A trick to reduce the space complexity is to notice that the recurrence relation doesn't need anything other than $$$dp_{i + 1}$$$ when calculating $$$dp_i$$$. Therefore, instead of creating a $$$dp$$$ array, we can simply update the value of $$$dp_{i + 1}$$$ using a variable.

Here is how you might implement this in python:

def find_minimum(cur_ind, A):
	return min(A)

That is all. I hope you learned something!