Skip to main content

Arrays Hands-On: Warming Up

Traversals - 1

Hi folks, it's been long since the previous article came, isn't it? Honestly, I've been busy with some other stuff. Getting back to the discipline of 1 article everyday now, hope it goes as I'm quoting here.

From here on, we're going to start warming up a bit, a bit of stretching, shoulder rolls, some light jogging etc., before we move on to the workout.

Find the smallest & 2nd smallest element

As the problem statement says, given an array of integers, we need to write a function that simply returns a vector that contains the smallest element, and the second smallest element.

Now, if you read it carefully, you'll see that if the array = [1, 4, 1, 2], the smallest element, of course, will be 1, but the 2nd smallest element to be returned here isn't 1, but 2. So, even if the smallest element is present multiple times, the 2nd smallest has to be the next smallest element only, i.e. 2 in this case.

How to find just the smallest?

Smallest Element (in brief) - Don't look if you need just a hint For finding just the smallest element, what can be done is that we keep track of a variable, let's say, running_min, which is initialised with a huge number, and we keep updating it while iterating the array whenever we find a number that is smaller than the current value of running_min.

If there was a poll feature, I'd have definitely asked how many people understood the above explanation, and for how many was it a bouncer? But, until we build that feature, I'll assume that it's not very clear and explain it in a more detailed manner.

The idea (Smallest Element) - Look here for a hint

We want to find the smallest element in the array. Now, I think that an absolute beginner will also be able to guess that to do that, we'll have to look at all the array elements at least once.

Now, while looking at the elements, what we'll also need is to be able to keep track of the smallest element that we've looked at so far.

The tool(s) Now, the tool we'll use to iterate is our beloved for loop. The other important thing is to keep track of the smallest element; let's use an integer variable running_min for that.
Putting it together
  1. Initialise the variable running_sum with a huge number.
  2. Start iterating on the array.
  3. If, at any point, arr[i] < running_sum, then update the value of running_sum and make it equal to arr[i].
The last point is what ensures that the value of running_sum is always equal to the smallest element encountered so far.
Implementation (Smallest) 
int minElement(int a[], int n) {
	int running_min = INT_MAX;
	for(int i = 0; i < n; ++i) {
		if(a[i] < running_min)
			running_min = a[i];
	}
	return running_min;
}

Let's move on to the 2nd smallest

Now that we've already found the smallest element in the array, this should be pretty straight-forward.

How? We'll look through all the elements again and try to find the smallest element with a tiny difference. That difference is that whenever we encounter an element equal to the smallest element, we'll just ignore it.
Implementation (Smallest & 2nd Smallest) 
vector<int> minAnd2ndMin(int a[], int n) {
	int smallest = minElement(a, n), sec_smallest = INT_MAX;
	for(int i = 0; i < n; ++i) {
		if(a[i] == smallest)
			continue;
		if(a[i] < sec_smallest)
			sec_smallest = a[i];
	}

	if(sec_smallest == INT_MAX) // returning acc. to problem statement
		return {-1};

	return {smallest, sec_smallest};
}

Can't we calculate both in one go?

The short answer is that yes, we can and we will, we will...

The long answer

What if we keep track of not just the smallest element, but also the second smallest element while traversing?

Let's try and follow the steps mentioned below:
  1. Initialise smallest and sec_smallest with INT_MAX
  2. Keep traversing.
  3. If a[i] < smallest, then make sec_smallest = smallest and smallest = a[i]
  4. Otherwise, if a[i] < sec_smallest, then keep smallest as is, but make sec_smallest = a[i], how does it sound?

Let me try to elaborate the last 2 points a bit, the 2nd last point basically says that if so far we thought that 5 is the smallest element, but we just encountered a smaller element (let's say, 3), then now 5 will be second smallest, and 3 will be smallest now.

Try to demystify the last point on your own now.

Implementing the long answer 
vector<int> minAnd2ndMin(int a[], int n) {
	int smallest = INT_MAX, sec_smallest = INT_MAX;
	for(int i = 0; i < n; ++i) {
		if(a[i] < smallest) {
			sec_smallest = smallest;
			smallest = a[i];
		}
		else if(a[i] < sec_smallest) {
			sec_smallest = a[i];
		}
	}
	if(sec_smallest == INT_MAX)
		return {-1};
	return {smallest, sec_smallest};
}
Spoiler

The spoiler is that the above explanation & code is incorrect :)

If you just update sec_smallest as mentioned in the last point of long answer, then even if a[i] is equal to smallest, then also sec_smallest will be updated.

E.g. If you take the array {2, 3, 2, 4}, the answer should be 2 3 whereas the above code will print 2 2.

Below is the corrected code, all we need is to make sure that we update sec_smallest only if a[i] > smallest. Put some more thought into it if it's not absolutely clear. 

vector<int> minAnd2ndMin(int a[], int n) {
	int smallest = INT_MAX, sec_smallest = INT_MAX;
	for(int i = 0; i < n; ++i) {
		if(a[i] < smallest) {
			sec_smallest = smallest;
			smallest = a[i];
		}
		else if(a[i] > smallest and a[i] < sec_smallest) {
			sec_smallest = a[i];
		}
	}
	if(sec_smallest == INT_MAX)
		return {-1};
	return {smallest, sec_smallest};
}

Conclusion

Sometimes, the problems that seem really easy in the first go can also be a slight (or maybe a lot of) pain in the a**.