Forem: Eda

LeetCode Meditations: Conclusion

Eda — Sun, 29 Dec 2024 15:26:44 +0000

With some detours here and there, we have finished looking at the problems in the NeetCode Practice roadmap (which is also the classic old Blind 75 list).

Overall, we took a look at sixty-two problems, with fourteen chapter introductions.

I did not start out with specific rules for this series, or how it will take shape—for example, we have also used Python for the earlier examples, but gradually switched to TypeScript—but it was a great experience to dissect the solutions, and slowly grasp the components that go with them.

Although I have to say that eventually, with time, we might forget, and the concepts and the patterns we learned might disappear. But, that's not a problem in itself, because as you might have realized, if there is one idea that should stick with us with this project is that problems are best solved when they are broken into smaller parts.
And, as with anything else, writing, or talking to oneself (see duck debugging), works miracles.

Even though we live in an interesting timeline where some people might think writing (or, any other creative activity) doesn't seem to matter that much anymore since we have now artificial "brains" to do it, we can still appreciate its value when we ourselves engage in it (or, any other creative activity).

Well, to admit, writing about the solutions to programming interview questions that have already been solved turns into seemingly generic outputs after a while; however, committing to this project was, to me, very meaningful.
It was not only the solutions, but the ritual that went with writing this series — including preparing the GIFs in chapter introductions, the cover images, and finding the nature photographs that go with them.

Talking of which, the photographs in the cover images that accompany each post are in fact taken by actual human beings, and can be found in this Unsplash collection. Also, all the visual assets can be found in this repository.

Now, it's time to take a deep breath.

It was a beautiful adventure to undertake this project, and hopefully you found some value as well if you came across a post.

Have a beautiful journey ahead, and until then, happy coding.

LeetCode Meditations: Sum of Two Integers

Eda — Sat, 28 Dec 2024 20:33:44 +0000

The description given for Sum of Two Integers is very simple:

Given two integers a and b, return the sum of the two integers without using the operators + and -.

For example:

Input: a = 1, b = 2
Output: 3

Or:

Input: a = 2, b = 3
Output: 5

In the very last problem of this series, we will close off with adding two integers using bit manipulation instead of our beloved plus operator.

Adding two bits, either of which can only be 1 or 0, doesn't have many varying results.
If we're adding two bits which are 1 and 0 (or, 0 and 1), the result will be 1. If we're adding two 0 bits, the result is 0. If, however, we're adding two 1 bits, we have a carry — which means we have to write 0 in the output, but also carry a 1.

For example, adding 2 and 3 will result in 5, and we will have a carry value during the operation:

Without thinking about the carry value, the output we need to have after adding two bits resembles a lot like what we would have after an XOR operation. If we have different bits (0 and 1, or, 1 and 0), the output will be 1, otherwise 0 (adding 0 and 0, or, 1 and 1).

So, an XOR operation can help us with the output.

What about the carry?

We have a carry value only when both of the bits are 1 — which looks like an AND operation.

So, an AND operation can help us with the carry.

Also note that the carry value is shifted to the left, for which we also have a handy left-shift operator.

So, our output and carry can look like this:

let output = a ^ b;
let carry = (a & b) << 1;

We can keep modifying the two values we have, and keep going until we don't have any carry values left. We can modify a to be the output, and b to be the carry, and return a, which holds the final output at the end.

Overall, the final solution might look like this in TypeScript:

function getSum(a: number, b: number): number {
  // while we still have carry
  while (b !== 0) {
    let output = a ^ b;
    let carry = (a & b) << 1;
    a = output;
    b = carry;
  }

  return a;
}

Time and space complexity

Both a and b are constant values, and we also don't need an additional data structure whose size will grow proportionately to the input, so both our time and space complexities will be constant, $O (1)$ .

And, that is the final problem of LeetCode Meditations series! We will wrap it up with a conclusion in the next post — until then, happy coding.

LeetCode Meditations: Missing Number

Eda — Tue, 24 Dec 2024 13:28:38 +0000

Let's start with the description for this problem:

Given an array nums containing n distinct numbers in the range [0, n], return the only number in the range that is missing from the array.

For example:

Input: nums = [3, 0, 1]
Output: 2

Explanation: n = 3 since there are 3 numbers, so all numbers are in the range [0, 3]. 2 is the missing number in the range since it does not appear in nums.

Or:

Input: nums = [0, 1]
Output: 2

Explanation: n = 2 since there are 2 numbers, so all numbers are in the range [0, 2]. 2 is the missing number in the range since it does not appear in nums.

Or:

Input: nums = [9, 6, 4, 2, 3, 5, 7, 0, 1]
Output: 8

Explanation: n = 9 since there are 9 numbers, so all numbers are in the range [0, 9]. 8 is the missing number in the range since it does not appear in nums.

It's also stated that all the numbers of nums are unique.

One easy way to solve this is to get the total sum of the range, then subtract the sum of the given array. What is left will be the missing number.

It can be done using reduce to sum the numbers, like this:

function missingNumber(nums: number[]): number {
  return Array.from({ 
    length: nums.length + 1 
  }, (_, idx) => idx).reduce((acc, item) => acc + item, 0) 
  - nums.reduce((acc, item) => acc + item, 0);
}

First, we create an array with values from 0 to nums.length + 1 and get its sum, then subtract the sum of nums from it.

However, the time and space complexities will be $O (n)$ with this solution as we create an array for the range.

We can have a more (storage-wise) efficient solution using bit manipulation.
In fact, we can use an XOR operation to help us with that.

To remember, XOR results in 1 if both of the bits are different — that is, one of them is 0 and the other is 1.
When we XOR a number with itself, it will result in 0, as all the bits are the same.

For example, 3 in binary is 11, when we do 11 ^ 11 the result is 0:

const n = 3;
const result = n ^ n; // 0

In other words, an XOR operation of a number with itself will result in 0.

If we do XOR with each number in the array with the indices, eventually all of them will cancel out (result in 0), leaving only the missing number.

You might think that not all numbers are at their index, for example if nums is [3, 0, 1], it is obvious that 3 does not even have an "index 3" that can be associated with it!

For that, we can start by initializing our result to nums.length. Now, even if the missing number is equal to nums.length, we are handling that edge case.

let result = nums.length;

Also, XOR is commutative and associative, so it's not important at which index a number appears (or doesn't have one, like in the example above) — they eventually will cancel out.

Now, with a for loop, we can do the XOR using the bitwise XOR assignment operator:

for (let i = 0; i < nums.length; i++) {
  result ^= i ^ nums[i];
}

And, the final result is the missing number. The solution overall looks like this:

function missingNumber(nums: number[]): number {
  let result = nums.length;
  for (let i = 0; i < nums.length; i++) {
    result ^= i ^ nums[i];
  }

  return result;
}

Time and space complexity

The time complexity is again $O (n)$ as we iterate through each number in the array, but the space complexity will be $O (1)$ as we don't have any additional storage need that will grow as the input size increases.

Next up, we will take a look at the final problem of the entire series, Sum of Two Integers. Until then, happy coding.

LeetCode Meditations: Reverse Bits

Eda — Mon, 23 Dec 2024 12:19:50 +0000

The description for Reverse Bits is very brief:

Reverse bits of a given 32 bits unsigned integer.

There is also a note:

Note that in some languages, such as Java, there is no unsigned integer type. In this case, both input and output will be given as a signed integer type. They should not affect your implementation, as the integer's internal binary representation is the same, whether it is signed or unsigned.

In Java, the compiler represents the signed integers using 2's complement notation. Therefore, in Example 2, the input represents the signed integer -3 and the output represents the signed integer -1073741825.

For example:

Input: n = 00000010100101000001111010011100
Output:    964176192 (00111001011110000010100101000000)

Explanation: The input binary string 00000010100101000001111010011100 represents the unsigned integer 43261596, so return 964176192 which its binary representation is 00111001011110000010100101000000.

Or:

Input: n = 11111111111111111111111111111101
Output:   3221225471 (10111111111111111111111111111111)

Explanation: The input binary string 11111111111111111111111111111101 represents the unsigned integer 4294967293, so return 3221225471 which its binary representation is 10111111111111111111111111111111.

It's also stated that The input must be a binary string of length 32 in the constraints.

Since we know that the input is a 32-bit integer, we can easily calculate the reversed position of each bit. For example, the 0th one corresponds to the 31st, the 1st to the 30th, and so on.

But we're doing bit manipulation, which means we have to deal with each bit one by one.
So, we can run a for loop to do just that. Each time, we can shift the bit by the index to the rightmost position, which can look like this:

n >>> idx

Getting a bit (whether it is 0 or 1) can be easily done with an AND operation with 1.
If the bit is 0, 0 & 1 will result in 0.
If it's 1, 1 & 1 will result in 1.

Note
We can think of ANDing with 1 as the multiplicative identity (for example, $\cdot 1 = 7$ ).

First, we can get the bit:

for (let i = 0; i < 32; i++) {
  let bit = (n >>> i) & 1;

  /* ... */
}

Then, we need to put the bit we have in the reversed position. For that, we can left shift the bit, adding to the result as we do so:

let result = 0;

for (let i = 0; i < 32; i++) {
  /* ... */

  // put the bit to the reversed position
  let position = 31 - i;
  result += (bit << position);
}

We need to return the result as a 32-bit integer, to do that, we can do a trick using the unsigned right shift operator:

function reverseBits(n: number): number {
  /* ... */

  return result >>> 0;
}

And, the final solution looks like this:

function reverseBits(n: number): number {
  let result = 0;
  for (let i = 0; i < 32; i++) {
    let bit = (n >>> i) & 1;
    // put the bit to the reversed position
    let position = 31 - i;
    result += (bit << position);
  }

  return result >>> 0; // return as a 32-bit integer
}

Time and space complexity

We know that the input and our result are always 32-bit integers (and, we don't have to use any other additional data structure), we run a loop 32 times as well, which is a fixed number, so both the time and space complexities are $O (1)$ .

Up next, we'll take a look at Missing Number. Until then, happy coding.

LeetCode Meditations: Counting Bits

Eda — Sun, 22 Dec 2024 12:55:18 +0000

The description for Counting Bits says:

Given an integer n, return an array ans of length n + 1 such that for each i (0 <= i <= n), ans[i] is the number of 1's in the binary representation of i.

For example:

Input: n = 2
Output: [0, 1, 1]

Explanation:
0 --> 0
1 --> 1
2 --> 10

Or:

Input: n = 5
Output: [0, 1, 1, 2, 1, 2]

Explanation:
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101

The problem wants us to get the number of 1s of the binary representation of each number from 0 up to n.

The first solution I came up with was to create an array of length n + 1, fill it with values from 0 to n in binary...

const arr = Array.from({ length: n + 1 }, (_, i) => i.toString(2));

...and map each one to the number of 1 bits it has:

arr.map(j => {
  let result = 0;
  let binaryNumber = parseInt(j, 2);
  while (binaryNumber > 0) {
    binaryNumber &= binaryNumber - 1;
    result++;
  }
  return result;
});

Note that in the previous problem, we used a technique to count the number of 1 bits (or calculate its Hamming weight) — it's simply decreasing one lesser value from the number until it reaches 0:

let numberOf1Bits = 0;
while (binaryNumber > 0) {
  binaryNumber &= binaryNumber - 1;
  numberOf1Bits++;
}

We can chain the methods, and overall, the solution looks like this:

function countBits(n: number): number[] {
  return Array.from({ length: n + 1 }, (_, i) => i.toString(2)).map(j => {
    let result = 0;
    let binaryNumber = parseInt(j, 2);
    while (binaryNumber > 0) {
      binaryNumber &= binaryNumber - 1;
      result++;
    }
    return result;
  });
}

Or, we can write it more explicitly, pushing each count to the result array:

function countBits(n: number): number[] {
  let result = [];
  for (let i = 0; i <= n; i++) {
    let binaryNum = parseInt(i.toString(2), 2);
    let count = 0;
    while (binaryNum > 0) {
      binaryNum &= binaryNum - 1;
      count++;
    }
    result.push(count);
  }

  return result;
}

Time and space complexity

Counting the set bits has $\ n$ time complexity (in the worst case when all bits are set, the loop will run the number of bits in binaryNumber — the number of bits of the binary representation of number $n$ is $\ n$ ).
However, we also do it $n$ times, so overall, the time complexity will be $\ log \ n)$ .

The space complexity is $O (n)$ as the need for space for our result array increases as $n$ increases.

Next up, we'll take a look at Reverse Bits. Until then, happy coding.

LeetCode Meditations: Number of 1 Bits

Eda — Sat, 21 Dec 2024 21:45:05 +0000

Let's start with the description for this one:

Given a positive integer n, write a function that returns the number of set bits in its binary representation (also known as the Hamming weight).

For example:

Input: n = 11
Output: 3

Explanation: The input binary string 1011 has a total of three set bits.

Or:

Input: n = 128
Output: 1

Explanation: The input binary string 10000000 has a total of one set bit.

Or:

Input: n = 2147483645
Output: 30

Explanation: The input binary string 1111111111111111111111111111101 has a total of thirty set bits.

As we mentioned in the chapter introduction in the previous post, a set bit refers to a bit with the value of 1.

So, what we have to do is to count 1 bits.

One way to do it is to convert the number to a string, and just count the 1s. Or, we can convert that to an array and filter out the 0s, and get its length. But, there is another approach where we can use bit manipulation.

We can remove the set bits (bits that have the value 1) until the number becomes 0.

A good thing to know is that n - 1 is the rightmost set removed version of n.

For example, if n is 0010, n - 1 is 0001.

Or, if n is 0110, n - 1 is 0101.

Note
It does not matter whether `n - 1` introduces other `1`s because we are doing the AND operation to count the set bits. For example, if `n` is `0000`, then `n - 1` is `0111`. Their AND will be `0000`. Or, if `n` is `0010`, then `n - 1` is `0001`. The rightmost set bit of `n` is `0` in `n - 1`, and that's all that matters.

We can create a loop that runs as long as there are 1 bits in n, counting each one as we go.
Also each time, we can do an AND operation with n and 1 less of it (n & (n - 1)).

A simple TypeScript solution looks like this:

function hammingWeight(n: number): number {
  let result = 0;
  while (n > 0) {
    n &= (n - 1);
    result++;
  }

  return result;
}

Note
We are using the bitwise AND assignment operator to assign the value to `n`.

Time and space complexity

The time complexity is, I think, $\ n)$ — In the worst case when all bits are set, we'll run through the loop $\ n$ times (the number of bits in the binary representation of a number $n$ will be $\ n$ ).

The space complexity will be constant ( $O (1)$ ) as there is no additional memory usage that will increase as the input increases.

The next problem we'll take a look at is Counting Bits. Until then, happy coding.

LeetCode Meditations — Chapter 14: Bit Manipulation

Eda — Mon, 16 Dec 2024 13:54:28 +0000

Introduction
Bitwise operators
- AND (&)
- OR (|)
- XOR (^)
- NOT (~)
- Left shift (zero fill) (<<)
- Right shift (sign preserving) (>>)
- Right shift (unsigned) (>>>)
Getting a bit
Setting a bit
Resources

We are in the last chapter of this series, and it's finally time to take a brief look at bit manipulation.

As Wikipedia defines it, a bitwise operation operates on a bit string, a bit array or a binary numeral (considered as a bit string) at the level of its individual bits.

Let's first represent a number in binary (base 2). We can use toString method on a number, and specify the radix:

const n = 17;

console.log(n.toString(2)); // 10001

We can also parse an integer giving it a base:

console.log(parseInt(10001, 2)); // 17

Note that we can also represent a binary number with the prefix 0b:

console.log(0b10001); // 17
console.log(0b101); // 5

For example, these are the same number:

0b1 === 0b00000001 // true

All bitwise operations are performed on 32-bit binary numbers in JavaScript.
That is, before a bitwise operation is performed, JavaScript converts numbers to 32-bit signed integers.

So, for example, 17 won't be simply 10001 but 00000000 00000000 00000000 00010001.

After the bitwise operation is performed, the result is converted back to 64-bit JavaScript numbers.

Bitwise operators

AND (`&`)

If two bits are 1, the result is 1, otherwise 0.

Note
The GIFs below show the numbers as 8-bit strings, but when doing bitwise operations, remember they are converted to 32-bit numbers.

const x1 = 0b10001;
const x2 = 0b101;

const result = x1 & x2; // 1 (0b1)

OR (`|`)

If either of the bits is 1, the result is 1, otherwise 0.

const x1 = 0b10001;
const x2 = 0b101;

const result = x1 | x2; // 21 (0b10101)

XOR (`^`)

If the bits are different (one is 1 and the other is 0), the result is 1, otherwise 0.

const x1 = 0b10001;
const x2 = 0b101;

const result = x1 ^ x2; // 20 (0b10100)

NOT (`~`)

Flips the bits (1 becomes 0, 0 becomes 1).

const n = 17;

const result = ~n; // -18

Note
Bitwise NOTing any 32-bit integer `x` yields `-(x + 1)`.

If we use a helper function to see the binary representations, it is as we expected:

console.log(createBinaryString(n));
// -> 00000000 00000000 00000000 00010001

console.log(createBinaryString(result));
// -> 11111111 11111111 11111111 11101110

The leftmost bit indicates the signal — whether the number is negative or positive.

Remember that we said JavaScript uses 32-bit signed integers for bitwise operations.
The leftmost bit is 1 for negative numbers and 0 for positive numbers.
Also, the operator operates on the operands' bit representations in two's complement. The operator is applied to each bit, and the result is constructed bitwise.

Note that two's complement allows us to get a number with an inverse signal.
One way to do it is to invert the bits of the number in the positive representation and add 1 to it:

function twosComplement(n) {
  return ~n + 0b1;
}

Left shift (zero fill) (`<<`)

Shifts the given number of bits to the left, adding zero bits shifted in from the right.

const n = 17;
const result = n << 1; // 34


console.log(createBinaryString(17));
// -> 00000000 00000000 00000000 00010001

console.log(createBinaryString(34));
// -> 00000000 00000000 00000000 00100010

Note that the 32nd bit (the leftmost one) is discarded.

Right shift (sign preserving) (`>>`)

Shifts the given number of bits to the right, preserving the sign when adding bits from the left.

const n = 17;
const result = n >> 1; // 8


console.log(createBinaryString(17));
// -> 00000000 00000000 00000000 00010001

console.log(createBinaryString(8));
// -> 00000000 00000000 00000000 00001000

const n = -17;
const result = n >> 1; // -9

console.log(createBinaryString(-17));
// -> 11111111 11111111 11111111 11101111

console.log(createBinaryString(-9));
// -> 11111111 11111111 11111111 11110111

Right shift (unsigned) (`>>>`)

Shifts the given number of bits to the right, adding 0s when adding bits in from the left, no matter what the sign is.

const n = 17;
const result = n >>> 1; // 8


console.log(createBinaryString(17));
// -> 00000000 00000000 00000000 00010001

console.log(createBinaryString(8));
// -> 00000000 00000000 00000000 00001000

const n = -17;
const result = n >>> 1; // 2147483639

console.log(createBinaryString(-17));
// -> 11111111 11111111 11111111 11101111

console.log(createBinaryString(2147483639));
// -> 01111111 11111111 11111111 11110111

Getting a bit

To get a specific bit, we first need to create a bitmask.
We can do this by shifting 1 to the left by the index of the bit we want to get.
The result is the and of the binary number and the bitmask.

However, using JavaScript, we can also do an unsigned right shift by the index to put the bit in the first place (so that we don't get the actual value that is in that position, but whether it is a 1 or a 0):

function getBit(number, idx) {
  const bitMask = 1 << idx;
  const result = number & bitMask;

  return result >>> idx;
}

For example, let's try 13, which is 1101 in binary:

const binaryNumber = 0b1101;

console.log('Bit at position 0:', getBit(binaryNumber, 0));
console.log('Bit at position 1:', getBit(binaryNumber, 1));
console.log('Bit at position 2:', getBit(binaryNumber, 2));
console.log('Bit at position 3:', getBit(binaryNumber, 3));

/*
Output:

Bit at position 0: 1
Bit at position 1: 0
Bit at position 2: 1
Bit at position 3: 1
*/

Setting a bit

If we want to turn a bit to 1 (in other words, to "set a bit"), we can do a similar thing.

First, we can create a bitmask again by shifting 1 to the left by the index of the bit we want to set to 1.
The result is the or of the number and the bitmask:

function setBit(number, idx) {
  const bitMask = 1 << idx;
  return number | bitMask;    
}

Remember that in our example 13 was 1101 in binary, let's say we want to set the 0 at index 1:

const binaryNumber = 0b1101;
const newBinaryNumber = setBit(binaryNumber, 1);

console.log(createBinaryString(newBinaryNumber));
// -> 00000000 00000000 00000000 00001111

console.log('Bit at position 1:', getBit(newBinaryNumber, 1));
// -> Bit at position 1: 1

We briefly looked at bitwise operations, as well as getting/setting a bit. In this final chapter, we will take a look at five problems, starting with Number of 1 Bits. Until then, happy coding.

Resources

LeetCode Meditations: Non-overlapping Intervals

Eda — Mon, 09 Dec 2024 12:03:27 +0000

The description for Non-overlapping Intervals is:

Given an array of intervals intervals where intervals[i] = [start_i, end_i], return the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.

Note that intervals which only touch at a point are non-overlapping. For example, [1, 2] and [2, 3] are non-overlapping.

For example:

Input: intervals = [[1, 2], [2, 3], [3, 4], [1, 3]]
Output: 1

Explanation: [1, 3] can be removed and the rest of the intervals are non-overlapping.

Or:

Input: intervals = [[1, 2], [1, 2], [1, 2]]
Output: 2

Explanation: You need to remove two [1, 2] to make the rest of the intervals non-overlapping.

Or:

Input: intervals = [[1, 2], [2, 3]]
Output: 0

Explanation: You don't need to remove any of the intervals since they're already non-overlapping.

For this problem, NeetCode has a great solution that starts with sorting the intervals, as we did in the previous problem.
We can also initialize a variable to keep track of the number of removals.

intervals.sort((a, b) => a[0] - b[0]);

let numRemovals = 0;

Now that our intervals are sorted, we'll go through each one, checking whether they overlap or not. We'll keep track of the previous interval's end for that, so let's initialize a prevEnd variable that initially holds the first interval's end:

let prevEnd = intervals[0][1];

Note
For two intervals not to overlap, the start of one should be strictly larger than the end of the other or the end of the one should be strictly smaller than the start of the other, as mentioned in our chapter introduction.

In this problem, when the end of an interval is equal to the other's start, they are considered non-overlapping.

So, here we can say that two intervals will overlap if the start of one is strictly less than the end of the other. In that case, we'll update prevEnd to be the lesser value of the two ends so that we have a less chance of overlapping with the next interval. Otherwise, we'll continue as before:

for (let i = 1; i < intervals.length; i++) {
  // overlapping, update the previous end
  // (remove the interval with the larger end value 
  // so we have less chance of overlapping with the next one)
  if (intervals[i][0] < prevEnd) {
    numRemovals++;
    prevEnd = Math.min(prevEnd, intervals[i][1]);
  } else {
    prevEnd = intervals[i][1];
  }
}

Finally, we can return numRemovals:

function eraseOverlapIntervals(intervals: number[][]): number {
  /* ... */

  return numRemovals;
}

And, the final solution we have looks like this:

function eraseOverlapIntervals(intervals: number[][]): number {
  intervals.sort((a, b) => a[0] - b[0]);

  let numRemovals = 0;
  let prevEnd = intervals[0][1];

  for (let i = 1; i < intervals.length; i++) {
    // overlapping, update the previous end
    // remove the interval with the larger end value so we have less chance of overlapping with the next one
    if (intervals[i][0] < prevEnd) {
      numRemovals++;
      prevEnd = Math.min(prevEnd, intervals[i][1]);
    } else {
      prevEnd = intervals[i][1];
    }
  }

  return numRemovals;
}

Time and space complexity

Since we sort the intervals at the start, the time complexity will be $\ log \ n)$ . We don't have an additional data structure whose size will increase as the input size increases, so the space complexity is $O (1)$ .

Next up, we will start the last chapter of the series, Bit Manipulation. Until then, happy coding.

LeetCode Meditations: Merge Intervals

Eda — Sun, 08 Dec 2024 20:41:19 +0000

Let's start with the description for Merge Intervals:

Given an array of intervals where intervals[i] = [start_i, end_i], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.

For example:

Input: intervals = [[1, 3], [2, 6], [8, 10], [15, 18]]
Output: [[1, 6], [8, 10], [15, 18]]

Explanation: Since intervals [1, 3] and [2, 6] overlap, merge them into [1, 6].

Or:

Input: intervals = [[1, 4], [4, 5]]
Output: [[1, 5]]

Explanation: Intervals [1, 4] and [4, 5] are considered overlapping.

We can start by sorting the intervals first, so that we can compare them easily later:

intervals.sort((a, b) => a[0] - b[0]);

Also, we can initialize a result array which initially holds the first element of the newly sorted intervals:

let result = [intervals[0]];

We need to track the last merged interval's end to compare it with the start of the current interval we are looking at to check if they overlap.

Note
For two intervals not to overlap, the start of one should be strictly larger than the end of the other or the end of the one should be strictly smaller than the start of the other, as mentioned in our chapter introduction.

If they don't overlap, we can just add that interval to result. Otherwise, we need to update the "last end," effectively merging the intervals:

for (const interval of intervals) {
  const [currentStart, currentEnd] = [interval[0], interval[1]];

  // non-overlapping
  if (result[result.length - 1][1] < currentStart) {
    result.push(interval);
  // overlapping, update last end
  } else {
    result[result.length - 1][1] = Math.max(result[result.length - 1][1], currentEnd);
  }
}

And, the only thing left to do is to return the result:

function merge(intervals: number[][]): number[][] {
  /* ... */
  return result;
}

And, this is how our final solution looks like in TypeScript:

function merge(intervals: number[][]): number[][] {
  intervals.sort((a, b) => a[0] - b[0]);
  let result = [intervals[0]];

  for (const interval of intervals) {
    const [currentStart, currentEnd] = [interval[0], interval[1]];

    // non-overlapping
    if (result[result.length - 1][1] < currentStart) {
      result.push(interval);
    // overlapping, update last end
    } else {
      result[result.length - 1][1] = Math.max(result[result.length - 1][1], currentEnd);
    }
  }

  return result;
}

Time and space complexity

We are sorting intervals, and the built-in sort function has $\ log \ n)$ time complexity. (The looping is $O (n)$ , but the overall time complexity is $\ log \ n)$ ).

The result array can increase in size as the size of the input array intervals increases, therefore we have $O (n)$ space complexity.

Next up, we'll take a look at the last problem in the chapter, Non-overlapping Intervals. Until then, happy coding.

LeetCode Meditations: Insert Interval

Eda — Tue, 03 Dec 2024 09:19:33 +0000

The description for Insert Interval is quite explanatory:

You are given an array of non-overlapping intervals intervals where intervals[i] = [start_i, end_i] represent the start and the end of the ith interval and intervals is sorted in ascending order by start_i. You are also given an interval newInterval = [start, end] that represents the start and end of another interval.

Insert newInterval into intervals such that intervals is still sorted in ascending order by start_i and intervals still does not have any overlapping intervals (merge overlapping intervals if necessary).

Return intervals after the insertion.

Note that you don't need to modify intervals in-place. You can make a new array and return it.

For example:

Input: intervals = [[1, 3], [6, 9]], newInterval = [2, 5]
Output: [[1, 5], [6, 9]]

Or:

Input: intervals = [[1, 2], [3, 5], [6, 7], [8, 10], [12, 16]], newInterval = [4, 8]
Output: [[1, 2], [3, 10], [12, 16]]

Explanation: Because the new interval [4, 8] overlaps with [3, 5], [6, 7], [8, 10].

We can start with creating a result array to hold, well, the result:

let result = [];

Then, going through all the intervals, we need to check if we are to put our new interval before or after the current interval, or, if they are overlapping and therefore need to be merged.

As we have seen in the chapter introduction, two intervals don't overlap if the start of one is strictly larger than the other's end, or, if the end of one is strictly less than the other's start.

When those both cases are false, they overlap.

First, we can check whether newInterval comes before interval. In fact, if we first check for this (the "earliest" position we can find to place newInterval), we can return immediately with our newly constructed result.
This is also the greedy approach.

for (let i = 0; i < intervals.length; i++) {
  const interval = intervals[i];

  // newInterval is before interval
  if (newInterval[1] < interval[0]) {
    result.push(newInterval);
    return [...result, ...intervals.slice(i)];
  }
  /* ... */  
}

However, if newInterval comes after the current interval we are looking at, we can just push the current interval to our result:

for (let i = 0; i < intervals.length; i++) {
  /* ... */
  // newInterval is after interval
  else if (newInterval[0] > interval[1]) {
    result.push(interval);
  }
}

The last option is when they overlap, in that case, we need to merge the two intervals. We can create newInterval again with the minimum value of the intervals as the start, and the maximum value of them as the end of the new interval:

for (let i = 0; i < intervals.length; i++) {
  /* ... */
  // overlapping, create newInterval
  else {
    newInterval = [
      Math.min(newInterval[0], interval[0]),
      Math.max(newInterval[1], interval[1])
    ];
  }
}

Our loop currently looks like this:

for (let i = 0; i < intervals.length; i++) {
  const interval = intervals[i];

  // newInterval is before interval
  if (newInterval[1] < interval[0]) {
    result.push(newInterval);
    return [...result, ...intervals.slice(i)] 

  // newInterval is after interval
  } else if (newInterval[0] > interval[1]) {
    result.push(interval);

  // overlapping, create newInterval
  } else {
    newInterval = [Math.min(newInterval[0], interval[0]), Math.max(newInterval[1], interval[1])];
  }
}

We also need to push the latest newInterval that we created. And, at the end, we can just return the result:

function insert(intervals: number[][], newInterval: number[]): number[][] {
  /* ... */
  result.push(newInterval);
  return result;
}

Finally, the solution looks like this:

function insert(intervals: number[][], newInterval: number[]): number[][] {
  let result = [];
  for (let i = 0; i < intervals.length; i++) {
    const interval = intervals[i];

    // newInterval is before interval
    if (newInterval[1] < interval[0]) {
      result.push(newInterval);
      return [...result, ...intervals.slice(i)] 

    // newInterval is after interval
    } else if (newInterval[0] > interval[1]) {
      result.push(interval);

    // overlapping, create newInterval
    } else {
      newInterval = [Math.min(newInterval[0], interval[0]), Math.max(newInterval[1], interval[1])];
    }
  }

  result.push(newInterval);
  return result;
}

Time and space complexity

The time complexity will be $O (n)$ as we do constant operations for each item in the intervals array. The space complexity will be $O (n)$ as well as we keep a result array and its size will increase as the length of intervals increases.

Next up, we'll take a look at Merge Intervals. Until then, happy coding.

LeetCode Meditations — Chapter 13: Intervals

Eda — Mon, 02 Dec 2024 11:20:02 +0000

In this new chapter, we are going to take a look at three interval problems: insert interval, merge intervals, and non-overlapping intervals.

An interval simply has a start and an end. The easiest way to think about them is as time frames.

With intervals, the usual concern is whether they overlap or not.

For example, if we have an interval [1, 3] and another [2, 5], they are clearly overlapping, so they can be merged together to create a new interval [1, 5]:

In order for two intervals not to overlap:

the start of one should be strictly larger than the end of the other

newInterval[0] > interval[1]

the end of the one should be strictly smaller than the start of the other

newInterval[1] < interval[0]

If both of these are false, they are overlapping.

If they are overlapping, the new (merged) interval will have the minimum value from both intervals as its start, and the maximum as its end:

[
  min(newInterval[0], interval[0]),
  max(newInterval[1], interval[1])
]

Next up is the first problem in this chapter, Insert Interval. Until then, happy coding.

LeetCode Meditations: Longest Increasing Subsequence

Eda — Sun, 01 Dec 2024 14:38:45 +0000

The description for this problem simply states:

Given an integer array nums, return the length of the longest strictly increasing subsequence.

For example:

Input: nums = [10, 9, 2, 5, 3, 7, 101, 18]
Output: 4
Explanation: The longest increasing subsequence is [2, 3, 7, 101], therefore the length is 4.

Or:

Input: nums = [0, 1, 0, 3, 2, 3]
Output: 4

Or:

Input: nums = [7, 7, 7, 7, 7, 7, 7]
Output: 1

Similar to the previous problem in this series, we can look at a bottom-up dynamic programming approach here as well.

For each value in the nums array, the length of the largest subsequence we can have starting from index $i$ is either:

1 (that value itself)

1 + the number of the largest subsequence we can have starting from index $i + 1$ .

However, we can't include the second option if nums[i + 1] is less than nums[i].

First, we can start out by creating a dp array to hold the length of the subsequences we can have from each index of nums onwards. That is, dp[0] will have the length of the largest subsequence that we can have from nums[0] onwards, dp[1] has the length of the largest subsequence that we can have from nums[1] onwards, and so on:

let dp = Array.from({ length: nums.length }, () => 1);

Then, we can start iterating from the last index of nums backwards (as it is the simplest position where there is only one way to form a subsequence onwards, just taking the value itself):

for (let i = nums.length - 1; i >= 0; i--) {
 /* ... */
}

For each option, we can iterate from the next index to see if we can include the largest subsequence that can be formed from that index onwards, if so, we can get the maximum value between dp[i] and 1 + dp[j]:

for (let i = nums.length - 1; i >= 0; i--) {
  for (let j = i + 1; j < nums.length; j++) {
    if (nums[i] < nums[j]) {
      dp[i] = Math.max(dp[i], 1 + dp[j]);
    }
  }
}

Finally, we can return the largest value in dp:

function lengthOfLIS(nums: number[]): number {
  /* ... */
  return Math.max(...dp); 
}

And, the final solution looks like this:

function lengthOfLIS(nums: number[]): number {
  let dp = Array.from({ length: nums.length }, () => 1);

  for (let i = nums.length - 1; i >= 0; i--) {
    for (let j = i + 1; j < nums.length; j++) {
      if (nums[i] < nums[j]) {
        dp[i] = Math.max(dp[i], 1 + dp[j]);
      }
    }
  }

  return Math.max(...dp);
}

Time and space complexity

The time complexity is $O(n ^ 2)$ as we iterate through each item in nums for each item in nums.
The space complexity is $O (n)$ as we keep a dp array and its size will increase as the length of nums increases.

This was the last dynamic programming problem in this series. Next up, we will start a new chapter on intervals. Until then, happy coding.

Forem: Eda

LeetCode Meditations: Conclusion

LeetCode Meditations: Sum of Two Integers

Time and space complexity

LeetCode Meditations: Missing Number

Time and space complexity

LeetCode Meditations: Reverse Bits

Time and space complexity

LeetCode Meditations: Counting Bits

Time and space complexity

LeetCode Meditations: Number of 1 Bits

Time and space complexity

LeetCode Meditations — Chapter 14: Bit Manipulation

Table of contents

Bitwise operators

AND (&)

OR (|)

XOR (^)

NOT (~)

Left shift (zero fill) (<<)

Right shift (sign preserving) (>>)

Right shift (unsigned) (>>>)

Getting a bit

Setting a bit

Resources

LeetCode Meditations: Non-overlapping Intervals

Time and space complexity

LeetCode Meditations: Merge Intervals

Time and space complexity

LeetCode Meditations: Insert Interval

Time and space complexity

LeetCode Meditations — Chapter 13: Intervals

LeetCode Meditations: Longest Increasing Subsequence

Time and space complexity

AND (`&`)

OR (`|`)

XOR (`^`)

NOT (`~`)

Left shift (zero fill) (`<<`)

Right shift (sign preserving) (`>>`)

Right shift (unsigned) (`>>>`)