Algorithm Discovery Process

In previous lessons and throughout the Core Curriculum, we have learned how to use the PEDAC process as our main problem-solving tool. Earlier in this book, we explored various time complexities. In this assignment, we will delve into the algorithm discovery process and understand how PEDAC fits into it.

The PEDAC process has given us structure to help us understand problem requirements, create examples, analyze problems thoroughly, and develop a naive solution that meets the requirements. Despite moving forward with algorithm discovery, PEDAC remains essential as it guides us to arrive at the initial solution. The question then arises: What should we do after this initial solution?

Once we have coded the naive solution, the next step is to analyze its runtime and explore potential optimizations. This is where the algorithm discovery process comes into play.

Pushing the Big O curve down 1 level

One approach to the algorithm discovery process is to incrementally improve the efficiency of our solution by pushing down the Big O curve we discussed in previous assignments 1 level at a time.

Let's return to a problem that we have already solved in one of the previous assignments, "Find Pair".

// Given a list of numbers,
// find two numbers in the list that add up to ten
// and return them. If no such pair exists, return null.

// It is guaranteed that there is either exactly one pair of numbers
// that satisfies the condition, or no pairs at all.

// Test Cases:

console.log(findPair([2, 3, 9, 7])); // Output: [3, 7]
console.log(findPair([10, 6, -1, 2])); // null
console.log(findPair([1, 2, 5, 6])); // null
console.log(findPair([1, 3, 6, 10, 4, 5])); // [6, 4]
console.log(findPair([4, -5, 3, 15, 5])); // [-5, 15]

As we've already seen, the naive algorithm for this problem involves using two nested loops to iterate over the collection and check if any pair of elements sum to the target. If a valid pair is found, we return the pair as an array; otherwise, we return null. Here's the code for the naive solution in JavaScript:

function findPair(nums) {
  for (let firstIdx = 0; firstIdx <= nums.length - 2; firstIdx++) {
    let firstNum = nums[firstIdx];
    for (let secondIdx = firstIdx + 1; secondIdx <= nums.length - 1; secondIdx++) {
      let secondNum = nums[secondIdx];
      if (firstNum + secondNum === 10) return [firstNum, secondNum];
    }
  }
  return null;
}

The time complexity of this initial solution is quadratic, O(N^2), and the space complexity is constant, O(1).

To optimize the solution, we will aim to reduce the time complexity. Can we solve the problem in O(NlogN)? Typically, achieving logarithmic time complexity involves performing a binary search on a sorted collection. However, we need to return the pair in the same order as they appear in the array. Sorting the array would change the order of the elements, making this approach unsuitable.

What about O(N)? As we discussed in the previous assignment, linear time complexity means that the runtime of an algorithm grows linearly with the input size.

For the "Find Pair" problem, to solve it in linear time complexity, we need a way to check for the presence of the complement without iterating through all the remaining elements. Without using any additional data structures, achieving this in linear time is not possible.

We have already seen a solution with nested loops, so what other approaches can we consider?

Hash Tables

One powerful optimization technique is the strategic use of hash tables. By using a hash table (or an object in JavaScript), we can significantly improve the time complexity of certain algorithms. Retrieval from a hash table has a constant time complexity of O(1), allowing for quick lookups.

In the "Find Pair" problem, this additional data structure allows us to check for the complement in constant time O(1). By storing the elements of the array and their indices in the Map, we can quickly determine if a complement exists. This solution has a time complexity of O(N) and a space complexity of O(N).

Using hash tables, we can significantly improve time complexity by leveraging their constant-time retrieval property. However, it's important to note that this improvement comes at the cost of increased space complexity. We accept higher memory usage in exchange for faster data retrieval with hash tables.

Here's the code for the optimized solution:

function findPair(nums) {
  const numMap = new Map();
  const targetNumber = 10;

  for (let idx = 0; idx < nums.length; idx++) {
    const complement = targetNumber - nums[idx];

    if (numMap.has(complement)) {
      return [complement, nums[idx]];
    }

    numMap.set(nums[idx], idx);
  }

  return null;
}

Let's explain the solution step by step:

1. Create an empty Map called numMap. This Map will store the elements from the array as keys and their corresponding indices as values.

2. Start iterating through the nums array using a for loop. The loop variable idx represents the index of the current element.

3. Calculate the complement of the current number by subtracting it from the target value. Store the result in the complement variable.

4. Check if the complement exists as a key in the numMap using the has method.

5. If the complement exists in the numMap, it means we have found a pair of numbers that sum up to the target. Since complement has already been placed in our numMap, we know that complement appears first in our input array, and we can return [complement, nums[idx]].

6. If the complement does not exist in the numMap, we add the current number and its index to the numMap. This step ensures that we can look up the indices of previously encountered numbers when we encounter their complements later in the array.

7. Repeat steps 3 to 6 for each element in the nums array until we find a solution or reach the end of the array. If we make it to the end without returning a pair, it means there is no solution and we can return null.

Walkthrough

Let's go through the example array [4, -5, 3, 15, 5]. The target sum is 10 per the problem description.

Step 1: The first element we encounter is 4. The complement is 6, (10 - 4), but numMap is empty, so we add the element with its index as the value in the numMap and continue.

Step 2: The second element is -5. The complement is 15, (10 - (-5)), however, numMap only contains the number 4 in it, so we add the number -5 as the key with its index value 1 and, once again, continue.

Step 3: The third element is 3. The complement is 7, (10 - 3). The numMap doesn't contain number 7 so we add the number 3 as the key in the numMap, with its index 2 as a value, and continue.

Step 4: The fourth element is 15. The complement is -5, (10 - 15). The number -5 is in the numMap object, so we finally return the array of the two values, the complement of -5, which appeared first, and the current number, 15, creating our final result of [-5, 15].

---

Practice: Find Majority Element

We'll now practice the techniques learned so far using the "Find a Majority Element" problem. Try to solve the problem using the naive (brute-force) approach first, and then see if you can optimize the solution.

Problem Description

// Given an array of numbers, return its majority element.

// The majority element is the value in the array that appears
// as at least half of the elements in the array.

// It is guaranteed that only one majority element exists in the array.

// Test Cases:

console.log(findMajority([6, 4, 4, 6, 4]) === 4);
console.log(findMajority([4, 5, 2, 5, 5, 5, 1]) === 5);
console.log(findMajority([1, 2, 1, 2, 2, 1, 2]) === 2);
console.log(findMajority([1, 2, 3, 1, 4, 4, 1, 1]) === 1);
console.log(findMajority([5, 5, 5]) === 5);

// All test cases should log true