This mindset 🧠 shift is the ultimate secret to my success!

In partnership with

Hello and welcome back brave human being,

Before we dig into this problem, let me remind you that what you seek is seeking you.

Whether it is an internship, a return offer, or whatever you are currently looking for, it is looking for you too.

This mindset helped me get everything I’ve wanted in life, from internships to scholarships, and even my acceptance to Berkeley.

When you start blocking yourself, remember, your goal is already looking for you. 😉

Day 19: 540. Single Element in a Sorted Array

You are given a sorted array consisting of only integers where every element appears exactly twice, except for one element which appears exactly once.

Let’s dive in 🤿 :

How would you solve it linearly?

If your first instinct was to use a hash map, you are on the right track.

You could linearly iterate through the array, store the occurrences, and find the element that was used only once. This solution would be costly as we would have a time complexity of O(N) and a space complexity of O(N).

The array is sorted, how could you leverage it?

Using a binary search!

 Do you need a refresher?

Let’s think a bit more about the problem.

Each element appears twice, which means the first appearance of the element is at an even-numbered index. And its secondary appearance is in an odd index.

The element that appears only once would mess up that pattern.

Our job is to find it.

We start by defining our variables:

L=0
R=array.size()-1
Middle = (L+R)/2 

We’ll introduce a new variable:

This variable will represent if the middle index is even.

Why is that relevant?

If we are at an even index, we can jump 2 indices, assuming the next index has the same number.

Otherwise, we can only jump one index, as the next index will have a different number.

What would be our stopping condition?

If the index is even, the next element is not repeated; if the index is odd, the previous element is not the same.

Let’s set an example:

Complete solution:

The time complexity of this solution would be O(Log N), making it significantly faster than our linear solution. 🤟 

See you Thursday for the next problem 😉 

Denisse

Learn how to make AI work for you.

AI breakthroughs happen every day. But where do you learn to actually apply the tech to your work? Join The Rundown — the world’s largest AI newsletter read by over 600,000 early adopters staying ahead of the curve.

1. The Rundown’s expert research team spends all day learning what’s new in AI

2. They send you daily emails on impactful AI tools and how to apply it

3. You learn how to become 2x more productive by leveraging AI

Subscribe with one click.