Blog

Day 1: Cache-Friendly Arrays, Alternate Elements & Leaders In An Array—DSA Diary

Day 1: Cache-Friendly Arrays, Alternate Elements & Leaders In An Array—DSA Diary

Learn why arrays love CPU caches, print alternate elements, and find “leader” values in O(n). Day 1 of my DSA Diary—code, pitfalls, and tips inside.

Today I started out with a problem but just when I got in I saw a line:

Day 1: Cache-Friendly Arrays, Alternate Elements & Leaders In An Array—DSA Diary

Cache Friendliness : Since items / references are stored at contiguous locations, we get the advantage of locality of reference.

Why are arrays cache-friendly?

  • In arrays, elements are stored in contiguous memory locations.
  • When you access arr[i], the CPU fetches that memory location and also nearby elements (because of cache lines).
  • So if you then access arr[i+1], arr[i+2], etc., chances are they’re already in cache → making it much faster.

Example

Imagine you have an array of integers:

[10, 20, 30, 40, 50, 60, 70, 80]
  • Accessing arr[0] loads 10 into cache and also 20, 30, 40 (same cache line).
  • When you later access arr[1] or arr[2], the CPU doesn’t go to RAM again – it just uses what’s already in cache.

Contrast with Linked List

  • A linked list stores elements at random memory addresses with pointers.
  • When you move from one node to the next, there’s no guarantee the next node is in the same cache line.
  • This leads to more cache misses, making linked list traversal slower in practice, even if both have O(n) complexity.

An array is not useful in places where we have operations like insert in the middle, delete from the middle, and search in unsorted data.

  1. If you only search occasionally: Linear search in an array or linked list is fine.
  2. If you also need order + fast search: Use a balanced tree.
  3. If you don’t care about order and just want fastest search: Use a hash table.

Now, I can start solving the question.

Q1: Alternate elements of an array

Question credit article.

Given an array arr[], the task is to print every alternate element of the array starting from the first element.

Examples:

Input: arr[] = [10, 20, 30, 40, 50]
Output: 10 30 50
Explanation: Print the first element (10), skip the second element (20), print the third element (30), skip the fourth element(40) and print the fifth element(50).

Input: arr[] = [-5, 1, 4, 2, 12]
Output: -5 4 12

Here, we seem to be printing elements at every even index. arr[0]=10, arr[2]=30, arr[4] =50

Start a loop at i = 0; increment i by 2 until i < n.

Time Complexity: O(n)

Auxiliary(extra) Space: O(1)

Click To View The Code 
#include<iostream>
using namespace std;

void printAlternate(int arr[],int size)
{
	for(int i = 0; i<size; i+=2)
	{
		cout<<arr[i]<<" ";
	}
}
int main() {
    int arr[] = {10, 20, 30, 40, 50};
    int n = sizeof(arr) / sizeof(arr[0]); 
    printAlternate(arr, n);
}

The article shows it can be worked out using recursion. I don’t get why an extra function was created.

Let’s try AI to help.

It was for making the process of taking input from the main method cleaner.

And doing it using the raw array is quite unnecessarily complex. So let’s use a vector instead.

Click To View The Code 
#include<iostream>
#include<vector>
using namespace std;

void getAlternate(vector<int> &arr, int idx, vector<int> &res)
{
	//This is the main recursion method.
	if(idx<arr.size()) 
	{
		res.push_back(arr[idx]);
		idx = idx + 2;
		getAlternate(arr, idx, res);
	}
}

void printAlternate(vector<int> &arr)
{
	//This method is to take input elegantly and provides the output elegantly.
	vector<int> res;
	getAlternate(arr, 0, res);
	
	for(int i = 0; i< res.size(); i++) {
		cout<<res[i]<<" ";
	}
}
int main() {
    vector<int> arr = {10, 20, 30, 40, 50};
    printAlternate(arr);
}

Time Complexity: O(n)

Auxiliary(extra) Space: O(n) (for the recursive calls and for the res vector)

We could have printed without the need for res. and extra method. Yet space complexity will be O(n) cause of recursion.

Click To View The Code 
#include<iostream>
#include<vector>
using namespace std;

void printAlternate(vector<int> &arr, int idx)
{
	if(idx<arr.size()) {
		cout<<arr[idx]<<" ";
		idx += 2;
		printAlternate(arr, idx);
	}
}

int main() {
	vector<int> arr = {10, 20, 30, 40, 50};
  printAlternate(arr, 0);
	return 0;
}

Interview tip: When recursion is used where iteration suffices, prefer iteration unless recursion unlocks some divide-and-conquer property.

Q2: Leaders in an array

Question credit article.

Given an array arr[] of size n, the task is to find all the Leaders in the array. An element is a Leader if it is greater than or equal to all the elements to its right side.

Note: The rightmost element is always a leader.

Examples:

Input: arr[] = [16, 17, 4, 3, 5, 2]
Output: [17 5 2]
Explanation: 17 is greater than all the elements to its right i.e., [4, 3, 5, 2], therefore 17 is a leader. 5 is greater than all the elements to its right i.e., [2], therefore 5 is a leader. 2 has no element to its right, therefore 2 is a leader.

Input: arr[] = [1, 2, 3, 4, 5, 2]
Output: [5 2]
Explanation: 5 is greater than all the elements to its right i.e., [2], therefore 5 is a leader. 2 has no element to its right, therefore 2 is a leader.

I couldn’t even think the two loops approach at first maybe I was too tired but when I let it set for a while and tried again I could think of the brute force.

The very first approach I tried was obviously two loops.

  1. Pick the first number.
  2. Check if it is greater than all the numbers on its right.
  3. If it is add it to a new list.
  4. Else move on even if you find one greater number.
Click To View The Code 
#include<iostream>
#include<vector>
using namespace std;

void printLeaders(vector<int> &arr)
{
	vector<int> res;
	for(int i =0; i<arr.size(); i++) {
		int flag = 1;
		for(int j = i+1; j<arr.size(); j++) {
			if(arr[i]<arr[j]) {
				flag = 0; break;
			}
		}
		if(flag==1) {
			res.push_back(arr[i]);
		}
	}

	for(int i = 0; i<res.size(); i++) {
		cout<<res[i]<<" ";
	}
}

int main() {
	vector<int> a = {16, 17, 4, 3, 5, 2};
	printLeaders(a);
	return 0;
}

Time Complexity: O(n^2)

Auxiliary(extra) Space: O(n)

I didn’t know the next one upright; I had to learn it first.

Another approach, which will take O(n) time, is:

  1. Iterate from the right end.
  2. Now add the first element to the result and keep it in a variable called highest.
  3. If the element is greater than highest append it to the start of list.
Click To View The Code 
#include<iostream>
#include<vector>
using namespace std;

void printLeaders(vector<int> &arr)
{
	vector<int> res;
	int highest = arr[arr.size()-1];
	for(int i = arr.size()-1; i>=0; i--) {
		if(highest<= arr[i]) {
			highest = arr[i];
			res.insert(res.begin(),highest);
		}
	}

	for(int i = 0; i<res.size(); i++) {
		cout<<res[i]<<" ";
	}
}

int main() {
	vector<int> a = {16, 17, 4, 3, 5, 2};
	printLeaders(a);
	return 0;
}

There’s a catch to this one. Because we are adding at the start instead of pushback:

res.insert(res.begin(), highest);

This can be O(n) each time, leading to amortized O(n²).

Better:

push_back into res during traversal (right-to-left), then reverse at the end.

reverse(res.begin(), res.end());

→ This keeps total time O(n).

Even when the core algorithm is O(n), data structure operations (like insert at front in vector) can silently add overhead. Always check.

That’s it for today see you tomorrow with some new problems

Leave a Reply