A week of LeetCode (day 1/7)

Photo by Christopher Gower on Unsplash

Acing the coding interview is key for landing your dream job. In particular, good technical interview skills often open the doors for many outstanding opportunities (FAANG included).

Many people struggle with coding interviews even if they used to get good grades in their Algorithms and Data Structures classes, mainly because they lack the experience of solving coding tasks.

But don’t worry, I have got your back with this series of 7 coding challenges on LeetCode.com. Their Difficulty will range from easy, medium, and hard and will cover a whole range of topics to equip you with all that you need.

Ready for the first challenge? Let’s dive in!

Day 1: Arithmetic Subarrays

I will assume you haven’t read the task description, so here is a summary:

You will be given a sequence S of n numbers, let’s denote the ith number of s by S[i-1], this is because the sequence is 0-indexed so the first element of S is S[0] and the last one is S[n -1]

The question we are trying to solve is given a range [L, R] of the sequence, can we order them somehow so that this range becomes an arithmetic sequence, and we need to answer m questions of that form.

A quick reminder :

A sequence of numbers is called arithmetic if it consists of at least two elements, and the difference between every two consecutive elements is the same. More formally, a sequence A is arithmetic if and only if A[i+1] - A[i] == A[1] - A[0] for all valid i.

For example, these are arithmetic sequences:

2, 4, 6, 8, 10
9, 9, 9,9
3, -1, -5, -9

The following sequence is not arithmetic:

2, 2, 3, 5, 7

So how do we find such an order?

A reasonable starting point is to think of what an arithmetic sequence looks like.

Hint: consider these arithmetic sequences :

1, 3, 5, 7, 9

-1, -4, -7, -10

3, 3, 3, 3, 3

Hopefully, you can distinguish three different types of arithmetic sequences:

1- an increasing sequence

2- a decreasing sequence

3- a fixed sequence

If you couldn’t get that observation, that’s okay, you are still off to a great start.

So if we can somehow fit our range into one of these types, then we can tell if it can be an arithmetic sequence or not.

So what should we do?

Well, have a look at the following sequence and read it:

-1, -4, -7, -10

No, I mean read it from right to left:

-10, -7, -4, -1

It turns out that it fits in our first category (the one with increasing sequences).

Any decreasing sequence can be an increasing one if reversed. We use that to our advantage by mapping each decreasing sequence to its reverse.

Now we still have the fixed sequence category and the reverse trick is not helpful anymore, since if you reverse a fixed sequence, it doesn’t change.

So we are going to tweak our definitions a bit, we can do so by considering non-decreasing sequences, noticing that any fixed sequence or increasing sequence is non-decreasing.

So, Ladies and Gentlemen, we have a winner. We can represent any arithmetic sequence by sorting it in non-decreasing order.

So our task becomes:

Given a sorted subarray S[L, R], is it an arithmetic sequence?

And it is easy to check that by applying the definition of the arithmetic sequence, that is to check if the difference between any two consecutive numbers is the same.

Let’s write some code:

Here is my python implementation:

And my C++ implementation:

Don’t forget to write the code yourself and experiment with it to make sure you clearly understand it.

So you have made it here, congratulations! You have just finished your first challenge, keep up the good work.

If you have questions for me, contact me on LinkedIn and follow me on Medium for more interesting articles.

That is all for today. Thanks for reading!