Blind 75

06.04.2022 — DataStructures, Algorithms, Blind75, LeetCode — 16 min read

Two Sum

Problem Statement:

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

Initial Thoughts:

Brute force search in `O(n^2)`:

Loop through each element x and find if there is another value that equals to target - x

Using Map:

For a more efficient way to check if the complement exists in the array - we can maintain a Map. For each element nums[i], we will store i for nums[i] as key. This will reduce the time down to O(n) but it will also have O(n) space complexity.

We can do better than going through the array twice. While we are constructing the Map we can check if its complement has already been inserted or not.

Solution:

1function twoSum(nums: number[], target: number): number[] {
2  const map = new Map<number, number>(nums.map((num, index) => [num, index]));
3  let answer: number[] = [];
4
5  nums.forEach((num, index) => {
6    const complementNumber = target - num;
7    const complementIndex = map.get(complementNumber);
8    if (typeof complementIndex === "undefined") return;
9    if (complementIndex === index) return;
10
11    answer = [index, complementIndex];
12  });
13
14  return answer;
15}

Longest substring without repeating characters

Problem Statement:

Given a string s, find the length of the longest substring without repeating characters.

Initial Thoughts:

Brute force:

Fix an initial starting index say i. Now search for all the substrings starting at index i and ending at index j where i <= j < s.length Now in this substring find if there are any repeating characters - if not check with the best answer so far and if it beats the best answer then consider this as the new best answer. The time complexity depends on how we are finding if there are any repeating characters in a string.

So the time complexity will be O(n ^ 2 * (cost of finding repeating characters))

Two pointer approach:

Keep a left pointer which starts from index 0. Initialise the right pointer also at index 0.

If the substring from left to right does not have repeating characters then we can increment the right pointer while the constraint is met. If the substring has repeating characters then we have two choices:

Either we keep incrementing the right pointer - but that doesn't make any sense because the string has repeated characters. Any more addition in the string will only make it contain repeated characters
Or we can increment the left pointer and hope to drop the repeating characters

Since in this approach, all the elements will be traversed at most twice - once by each left and right pointer. So the time complexity will be O(n * (cost of finding repeating characters))

I wouldn't have been able to solve this using two-pointer approach had I not watched the video from the Back to Back SWE.

But the main problem still remains to be solved: How do I find if a string has repeating characters or not?

1function hasRepeatingCharacters(s: string): boolean {
2  const seenCharacters = new Set([...s]);
3  return seenCharacters.size < s.length;
4}
5
6function lengthOfLongestSubstring(s: string): number {
7  let leftPointer = 0;
8  let rightPointer = 1;
9  let answer = 0;
10
11  while (rightPointer <= s.length) {
12    const substringToCheck = s.substring(leftPointer, rightPointer);
13    if (hasRepeatingCharacters(substringToCheck)) {
14      leftPointer += 1;
15      continue;
16    }
17    answer = Math.max(answer, substringToCheck.length);
18    rightPointer += 1;
19  }
20
21  return answer;
22}

Longest palindromic substring

I was lazy to write all my thoughts on this day since the problem was a bit difficult and I couldn't think about anything other than a bruteforce solution

Container With Most Water

Problem Statement:

You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]).

Find two lines that together with the x-axis form a container, such that the container contains the most water.

Return the maximum amount of water a container can store.

Initial Thoughts:

Brute force:

Pick all the possible pairs i and j. The answer is not dependent on how tall or short beams lies between them but only on the heights[i] and heights[j].

1let answer = 0;
2for (let i = 0; i < n; i++) {
3  for (let j = i + 1; j < n; j++) {
4    const area = (j - i) * Math.min(heights[i], heights[j]);
5    answer = Math.max(area, answer);
6  }
7}
8return answer;

Optimized Approach:

I could come up with this constraint but it wasn't that useful:

We want to maximise the product of distance between two lines and the difference of heights between two lines

Had to look at hints but still wasn't very clear how I could optimise the brute force solution, Hint:

Start with the maximum width container and go to a shorter width container if there is a vertical line longer than the current containers shorter line. This way we are compromising on the width but we are looking forward to a longer length container.

After looking at the hint I thought:

For any given range [L, R], we have two choices: [L + 1, R] and [L, R - 1]

We should move to L + 1 if heights[L] < maxHeights(L + 1, R)
We should move to R - 1 if heights[R] < maxHeights(L, R - 1)
If heights[L] === heights[R] - we can move to whoever has maximum among maxHeights(L + 1, R), maxHeights(L, R - 1)

And then I got stuck on how to construct the said maxHeights function

Solution:

Start the left pointer at the beginning and the right pointer at the end

If at any point heights[l] <= heights[r] then we move the left pointer by 1 in the right direction. Otherwise we move the right pointer by 1 in the left direction.

Proof of correctness:

Suppose our left pointer is at index i and our right pointer is at index j and S(i, j) is the current answer.

Say heights[i] <= heights[j] and we move to S(i + 1, j) In this case, we are omitting S(i, j - 1), S(i, j - 2) and so on till S(i, i + 1).

But for all such right pointers we have omitted, the minimum height would be heights[i] or even lesser than heights[i]. Also, the distance would be at least one less than what was between i and j and hence we are making our area lesser if we had decreased our right pointer in this case. Hence, there is no way that the omitted states will have better answer compared to S(i, j).

Same can be said about the other case: heights[j] < heights[i] and we move to S(i, j - 1) In this case we are omitting S(i + 1, j), S(i + 2, j) and so on till S(j - 1, j).

But for all such left pointers we have omitted, the minimum height would be heights[j] or even lesser than heights[j]. Also, the distance would be at least one less than what was between i and j and hence we are only making our area lesser if we had incremented our left pointer in this case. Hence, there is no way that the omitted states will have better answer compared to S(i, j).

The code for this approach can be found here.

You have two heights h[l] and h[r], and h[l] < h[r], then we know we have two choices, we want to move one of them. If we move the larger one, we cannot increase the height for the simple reason that we are always limited by the shortest, and we would be decreasing j - i, the width as well.

To clarify: let's say we kept the shortest forever, what would happen? Well, j - i would decrease, and either we come across a taller block, which doesn't matter because our shorter one we kept only mattered, or we find a shorter one, in which case that one matters. Either way we end up with a smaller area, so we must move the shorter one because moving the larger one cannot give an increase in area.

Trapping Rain Water

Problem Statement:

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

Initial Thoughts:

Pointer based approach - Failing for a particular edge case :'(

We need to first find the index of the "bar" which has non zero height, say x. Similarly, we need to find the index of the last bar which has non zero height, say y. We need to do this because we can't trap the water before these non-zero heighted bars.

We will initialise our left pointer L at x and our right pointer R at x + 1. Now, we will keep increasing our right pointer till we find the first bar which has height greater than height[L]. The way we have constructed our pointers, right now R is the first index in the [L, R] range for which height[L] < height[R] So, we can go ahead and assume a cube from L + 1 to R - 1 with length of ((R - 1) - (L + 1) + 1) = (R - L - 1) and height of height[L] and width 1. This is the raw volume assuming that in the range L + 1 to R - 1 we have zero heighted bars in between. We need to compensate for those bars and we will do that by looping from L + 1 to R excluding R and subtracting height of all the bars in between. This will give us the water that can be trapped in the range [L, R].

As soon as we have added the amount in the answer, we will set our left pointer to R and right pointer to R + 1 and keep searching for this till our right pointer is less than or equal to y.

But there's an edge case in this approach. There can be a case where our R has reached y but the left pointer L is still stuck at the maximum value somewhere. We need to count the volume in between if water can be trapped in between. The water can only be trapped in this last range if there exists a minima in [L, R] otherwise if it is decreasing then no water can be trapped in between.

Sadly, this is the part where I got stuck and couldn't think of any way to implement this.

Final Solution:

I am yet to go through the solution so hopefully I will update it later hopefully!

3Sum

Problem Statement:

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Initial Thoughts:

Pointer based approach:

Since we only need to find the triplets and the order doesn't matter, we can sort our array. After sorting the array, we can loop from index i = 0 till i + 2 < nums.length and our task boils down to finding two numbers in the remaining sorted array whose sum add upto -nums[i].

This sub-problem can be solved using two pointers where we initialise our left pointer L as i + 1 and the right pointer R as nums.length - 1. If sortedNums[L] + sortedNums[R] > -sortedNums[i] then that means we have to lower our right pointer because increasing L pointer in this case will only make the sum go high. If sortedNums[L] + sortedNums[R] < -sortedNums[i] then that means we have to increase our left pointer because decreasing R pointer in this case will only make the sum go down. And finally if sortedNums[L] + sortedNums[R] === sortedNums[i] then we have found the triplet where i != L != R and their sum is 0.

But we still need to get rid of the duplicate triplets. For example, if the nums array is [1, -1, -1, 0] then our above algorithm will report two triplets [[-1, 0, 1], [-1, 0, 1]]. This is happening because there are two distinct indices for -1 which can be paired up with 0 and 1.

So, to remove the duplicate triplets, I came up with a very naive solution: I kept track of all pairs seen for a particular sortedNums[i] if a triplet was found. And if there existed pairs corresponding to sortedNums[i] I checked if any of the pair's first number was sortedNums[leftPointer] If yes then [sortedNums[i], sortedNums[leftPointer], sortedNums[rightPointer]] is already "seen" and has already been added to the answer and we can ignore this.

This solution is not memory efficient and may add extra overhead too when we are comparing it will all the "seen" triplets but it works.

The code for this naive approach can be found here.

Final Solution:

An important thing to note here is that the triplet can only be repeated if we have multiple entries for either nums[i] or nums[leftPointer] or nums[rightPointer] or all of the three. So, we can do a little bit better by:

Moving i to the last occurrence for that particular number.
Once found the answer:
- Keep increasing L so that we skip all multiple entries for sortedNums[L].
- Keep decreasing R so that we skip all multiple entries for sortedNums[R]. and resume the search in now updated [L, R] range.

The code for this appproach can be found here.

Top k frequent elements

Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.

Initial Thoughts:

Using Map to count frequency and then using buckets to store numbers with a particular frequency:

Loop through all the numbers in the nums array and maintain a numberToFrequency map. Make an array of size 1 + nums.length and call it frequencyToNumbers, the entries will be an array of integers itself. This will essentially serve as a reverse lookup table where the index will be a particular frequency and we will get how many numbers were preesnt in nums array with that particular frequency. Once the said array is constructed, we will initialise an answer array and we will loop through the frequencyToNumbers array it the reverse order - starting from the highest frequency till the frequency 1 and keep pushing all the elements for a particular frequency in the answer array. We will keep pushing till the size of the answer array is not equal to k.

Time complexity: O(N) to construct numberToFrequency map plus O(N) to construct the frequencyToNumbers array and then O(N) in the worst case to loop through the frequencyToNumbers array and filling up the answer array.

Space complexity: O(N) for numberToFrequency map plus O(N) to for the frequencyToNumbers array.

The code for this approach can be found here.

Final Solution:

Using Heap:

We can also solve this using Heap datastructure. The detailed explanation of the heap datastructure can be found here. There you can also find the solution of this problem using heaps.

Remove Nth Node From End of List

The detailed solution for this problem can be found in this post

Valid Parentheses

Problem Statement:

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.

Solution:

This is the classic example of how Stack can be used. Whenever we encounter a closing bracket, we need to check it with the last opening bracket. To remeber the last opening bracket, we can use the Stack data structure and whenever we encounter an opening bracket, we just push it on the stack to retrieve it later.

In the end, we just need to check if there are no opening brackets left in the stack - if there are, then that means that we have excess of opening brackets and string is not valid.

The code for the above approach can be found here.

Merge Two Sorted Lists

Problem Statement:

You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists in a one sorted list. The list should be made by splicing together the nodes of the first two lists.

Return the head of the merged linked list.

Solution:

First of all, we start by creating a dummy node for the merged list - mergedListHead. We initialise a firstPointer by setting it to point to the head of the first list and similarly initialise secondPointer by setting it to point to the head of the second list. We also keep a lastNode to point to the last node we have inserted in the merged list and initialise it by setting it to mergedListHead.

Then, we start looping till we have traversed both the lists and added all nodes in the merged list. During each iteration, we check:

If we have firstPointer and secondPointer we make lastNode.next point to the smaller of these two.
Then we set the lastNode to point to the smaller node that we have just inserted.
And at last, to keep things moving, we increment the smaller node to point to its next node.

If either of the firstPointer or secondPointer has reached null, we make sure to add all the nodes from the remaining list so that we cover all the elements.

The code for the above approach can be found here.

Merge `k` Sorted Lists

Problem Statement:

You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.

Merge all the linked-lists into one sorted linked-list and return it.

Solution:

Brute Force solution:

First of all, we start by creating a dummy node for the merged list - mergedListHead. We also keep a pointer lastInsertedNode and initialise it with mergedListHead.

Then, during each iteration, we start by finding the minimum out of all k lists' head say minimumNode and the list's index in the original lists array say min. We insert the said minimum node in the list by setting lastInsertedNode.next to minimumNode. We update the lastInsertedNode as minimumNode and we go to the lists[min] and set it to lists[min].next and essentially popping it out.

Time complexity: O(kN) where N is the total number of nodes in all the lists combined. The factor of k comes in because for inserting each node we have to go and compare all k heads of all lists.

The code for the above approach can be found here.

Optimized solution using MinHeap:

The detailed explanation of the MinHeap datastructure and the solution using MinHeap can be found here.

Search in Rotated Sorted Array

Problem Statement:

There is an integer array nums sorted in ascending order (with distinct values).

Prior to being passed to your function, nums is possibly rotated at an unknown pivot index k (1 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). For example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2].

Given the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.

You must write an algorithm with O(logN) runtime complexity.

Solution:

Binary Search:

After the rotation, the nums array can be thought of as partitioned into three regions: [...x, pivot, ...y]. The region x is sorted in ascending order and also the combined region [pivot, ...y] is sorted in ascending order. Because nums had distinct values, all the numbers in the x region are strictly greater than pivot and all the numbers in the y region.

Hence, if we want to find target in nums array, we can either find it in the x region via binary search or in the [pivot, ...y] region via binary search. And this will require us to find the index of the pivot first.

Finding index of pivot:

We are interested in finding index of the pivot element say i. Notice that pivot < y[0] and pivot < x[x.length - 1]. So, if we were to apply binary search to find the index of pivot, our base case would be finding mid such that arr[mid] < arr[mid + 1] and arr[mid] < arr[mid - 1]. And at each step, we can also prune the half of the search space, how?

If arr[mid] > arr[high] then we know that this can only happen if arr[mid] is in the x region and the pivot can only be found in the [mid + 1, high] region. And if arr[mid] < arr[high] then we know that this can happen if arr[mid] is in the [pivot, ...y] region. It is possible that arr[mid] is the pivot so we store it as a potential answer and keep searching in the [low, mid - 1] region This is so for the case when arr[mid] is in y region and not equal to pivot.

So, since we are able to correctly prune the search space by half, we can use binary search in finding the index of pivot.

Finding index of target: Once we have found the index of pivot, we are just left with the task of finding target in nums.slice(0, pivotIndex) and nums.slice(pivotIndex). If target is not found in the either of the region, we return -1.

Time complexity: O(logN) to find the index of pivot. O(logN) to find the target in the two sorted sub-arrays of nums

The code for the above approach can be found here.

Combination Sum

Problem Statement:

Given an array of distinct integers candidates and a target integer target, return a list of *all unique combinations* of candidates where the chosen numbers sum to target. You may return the combinations in any order.

The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if the frequency of at least one of the chosen numbers is different.

It is guaranteed that the number of unique combinations that sum up to target is less than 150 combinations for the given input.

Solution:

Recursive Approach:

First of all, we sort all the candidates in ascending order.

Let's say we are considering whether to include candidates[0] in building the target or not. If we choose to include candidates[0] to include in the target then we need to see if target - candidates[0] can be build from candidates[0:] since repeatations are allowed. If we choose to exclude candidates[0] then our job is to find if we can build target from candidates[1:] onwards.

To generalise,

1canBuild(candidates[i:], target) = canBuild(candidates[0:], target - candidates[i])
2  || canBuild(candidates[(i + 1):], target)

The base condition will be:

If target < 0 then we will return false.
If target === 0 then we return true.
If i >= candidates.length and target > 0 then we return false.

The above recurrence relation with the base cases just tells us if it is possible to generate target from all candidates or not. We actually need to find all the combinations too. How do we find the combinations?

For this, we maintain a global answer array where we will store all the combinations and we keep an array of current combinations at each step. If target === 0 then we push the current combination array in the answer array. But this will lead to pushing duplicate combinations having same frequency if the recurrence relation logic is kept the same. This is because let's say the candidates array is [2, 3] and target is 7. Then there are two paths that will lead us to 7:

Pick candidates[0], candidates[0] and then candidates[1]
Pick candidates[1], candidates[0] and then candidates[0] again.

How do we avoid these duplicate combinations?

Suppose, there was a combination containing candidates[i] that led to target. Either this combination would have been found by our exhaustive search when we were at index j < i, or candidates[i] would have been the first one in the combinations array.

Hence, we can avoid searching from 0 again when we pick an element candidates[i] and keep searching for answer from i itself.

Time complexity: At each step, we have two choices.

The code for the above approach can be found here.

Rotate Image

Problem Statement:

You are given an n x n 2D matrix representing an image, rotate the image by 90 degrees (clockwise).

You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.

Initial thoughts:

After looking at the above image and tracking each element, we can see a pattern here that:

an element in the jth column goes to jth row and
an element in the ith row goes to n - 1 - ith column.

In general, an element (i, j) goes to (j, n - 1 - i).

I was able to derive the above pattern on my own and using the above pattern, we can derive the rotated matrix of size n x n but that would have consumed extra space and wouldn't satisfy the constraint that we need to do this in-place - without using extra memory.

Solution:

Seeing rotation as composition of transformations:

We can see that the 90 degree clockwise rotation is nothing but a composition/chaining of 2 transformations:

An element at (i, j) goes to (j, i) - also commonly known as transpose
Element at (i, j) goes to (i, n - 1 - j) - vertical reflection

Our original rotation is nothing but an element going to its transpose position and from there going to its reflection: (i, j) -> (j, i) -> (j, n - 1 - i).

The code for the above approach can be found here.

Rotate Groups of Four Cells:

We can see that element at (i, j) goes to (j, n - 1 - i) which goes to (n - 1 - i, n - 1 -j) which goes to (n - 1 - j, i) which finally goes to (i, j). So what we can do is:

1const temp = matrix[n - 1 - j][i];
2// Update fourth element by third
3matrix[n - 1 - j][i] = matrix[n - 1 - i][n - 1 - j];
4// Update third element by second
5matrix[n - 1 - i][n - 1 - j] = matrix[j][n - 1 - i];
6// Update second element by first
7matrix[j][n - 1 - i] = matrix[i][j];
8// Update first element by fourth
9matrix[i][j] = temp;

The main challenge in this approach is how to execute the above swaps in a loop so that all elements are touched only once.

For this let's say we are looking at n x n matrix right now. Let's say we are going to handle the elements of just the 0th row for now.

Let's say we loop from the 0th column and go on till the (n - 2)th column (0-based indexing). If we rotate any element matrix[0][j] then for that we will end up rotating the corresponding element on the (n - 1)th column, (n - 1)th row and 0th column according to the above logic. And after we are done rotating all such element matrix[0][j] where 0 <= j < n - 1 we will have taken care of the outermost layer of the n x n matrix, and we will be left with rotating remaining (n - 2) x (n - 2) matrix.

More generally, if we are solving for a k x k sub-matrix, at any element left + i in the top row, matrix[top][left + i] will go to matrix[top + i][right] that will go to matrix[bottom][right - i] and that will go to matrix[bottom - i][left] which will eventually go back to matrix[top][left + i] for all 0 <= i < (right - left).

Here top and bottom are the first and last rows and left and right are the first and last columns respectively of the k x k sub-matrix of an n x n sub-matrix. Formally, top = k - 1, left = k - 1, right = n - k bottom = n - k in a zero based indexing. For example, if we looking at the inner 2 x 2 matrix then top = left = (2 - 1) = 1 and right = bottom = (4 - 2) = 2. Once we are done with handling k x k sub-matrix we move on to handle (k - 2) x (k - 2) sub-matrix of this k x k sub-matrix.

The code for the above approach can be found here.

This is a great video from NeetCode channel illustrating the above approach visually.

Group Anagrams

Problem Statement:

Given an array of strings strs, group the anagrams together. You can return the answer in any order.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Initial thoughts:

Using a HashMap:

Since all anagrams have same characters and same frequency for each character, their sorted strings are equal. This sorted string can be used as a representative string and this can be used as a key in the HashMap.

The code for the above approach can be found here.

Solution:

Using frequency as a key in the HashMap:

We can transform each string s into a tuple of 26 non-negative integers representing the number of all characters. We can then join the entries of this tuple via a delimiter such as # and use the resulting string as the key in the HashMap.

Maximum Subarray

The detailed solution for this problem can be found in this post

Spiral Matrix

Problem Statement:

Given an m x n matrix, return all elements of the matrix in spiral order.

Initial thoughts:

This problem can be solved using the same approach as Rotate Image problem. First of all, we start with the top, left, right and bottom pointers. We initialise top pointer as 0, the bottom pointer as m - 1, the left pointer as 0 and the right pointer as n - 1. Then for given set of these four pointers, we need to traverse the elements in this order:

All elements of the top row from left to right column and increment the top pointer by 1.
All elements of the right column from the updated top (prevTop + 1) to the bottom row and decrease the right pointer by 1.
All elements of the bottom row from the updated right (prevRight - 1) to left column only if top <= bottom, and decrease the bottom pointer by 1.
Finally, all the elements of the left column from the updated bottom (prevBottom - 1) to updated top (prevTop - 1) row only if left <= right.

These if conditions in the 3rd and 4th step are to make sure we don't overcount.

This way, we'd have taken care of all the elements in the outer layer and we simply need to focus on the inner remaining matrix.

The code for the above approach can be found here.

Blind 75

.css-1bw77fa{color:var(--theme-ui-colors-primary);-webkit-text-decoration:none;text-decoration:none;}.css-1bw77fa:hover{-webkit-text-decoration:underline;text-decoration:underline;}Two Sum

Problem Statement:

Initial Thoughts:

Brute force search in O(n^2):

Using Map:

Solution:

Problem Statement:

Initial Thoughts:

Brute force:

Two pointer approach:

Problem Statement:

Initial Thoughts:

Brute force:

Optimized Approach:

Solution:

Proof of correctness:

Problem Statement:

Initial Thoughts:

Pointer based approach - Failing for a particular edge case :'(

Final Solution:

Problem Statement:

Initial Thoughts:

Pointer based approach:

Final Solution:

Initial Thoughts:

Using Map to count frequency and then using buckets to store numbers with a particular frequency:

Final Solution:

Using Heap:

Problem Statement:

Solution:

Problem Statement:

Solution:

Problem Statement:

Solution:

Brute Force solution:

Optimized solution using MinHeap:

Problem Statement:

Solution:

Binary Search:

Problem Statement:

Solution:

Recursive Approach:

Problem Statement:

Initial thoughts:

Solution:

Seeing rotation as composition of transformations:

Rotate Groups of Four Cells:

Problem Statement:

Initial thoughts:

Using a HashMap:

Solution:

Using frequency as a key in the HashMap:

Problem Statement:

Initial thoughts:

Two Sum

Brute force search in `O(n^2)`: