Using Two Sum Problem IRL: Implementing Search functionality using JavaScript

Algorithms and data structures are fundamental building blocks in software development. Although the idea of optimizing performance and delivering excellent results is intriguing, the repetitive and tedious process of learning codes and algorithms can be demotivating. However, there is an alternative approach to make learning more engaging by understanding the practical applications of algorithms and data structures in real-world situations.

In this second article of the series, we will explore the practical application of the popular Leetcode question “Two Sum” in developing search functionality for web applications using JavaScript. Let us dive in and make the learning journey more exciting!

Introduction

Imagine you’re a librarian in a large library with thousands of books categorized into different sections. One of the major tasks is to keep track of the availability of books in each section and assist library patrons in finding their desired books. To make this process efficient, you can use the Two Sum algorithm to implement search functionality. Here’s how:

First, you start by creating an index of all the books available in your library, along with their corresponding section numbers. When a patron enters a search query for a book, the Two Sum algorithm (two pointer approach) comes into play by scanning through the index to find the section that contains books matching the query. For instance, if a patron wants to borrow a book on “World History,” the two pointer algorithm will quickly scan through the index and find the section number that contains books on “World History.” This way, you can easily locate the book for the patron without having to search through each section of the library manually.

Confused? Let me try to explain it to you like you are 5.

Imagine you have a toy box with different kinds of toys. Now, suppose your friend asks you to find a specific toy, let’s say a red car. It would take a lot of time and effort to go through the entire toy box to find the red car. But if you have a list of all the toys in the toy box, along with where each toy belongs – your task will become significantly easier. For example, the red car is in the car section of the toy box. This way, when your friend asks for a red car, you can use the list to quickly find the car section and then look for the red car in that section.

The two pointer algorithm works similarly. In a library, there are many books and each book belongs to a certain section, like history or science. Instead of searching through all the sections to find a specific book, we can make a list of all the books and their corresponding sections. When someone asks for a book, we can quickly use the two pointer algorithm to find the section where the book is located. This makes it easier and faster to find the book, just like finding the red car in the toy box.

Sounds good? Let’s now understand the technicalities of this approach and its real-life implementation – in search functionality using JavaScript.

Two Sum Approach

Let’s take an example of a simple array that has only 4 elements – 2,7,11 and 15 (notice how the array elements are presented in sorted order). We have to now find out a pair of numbers in this array that add up to a certain target, let’s say that the target’s value is 9.

There are different ways of solving this problem, however, we will be discussing today a methodology which is called the two-pointer approach. As the name suggests, there are two pointers that come into the picture – let’s say the first pointer is called left and the second pointer is called right. We start by placing the left pointer at the start of the array and the right pointer at the end of the array.

Here is the general idea of how the pointers move:

If the number present at left and the number present at right positions add up to more than what the target is, we decrease the right pointer. How? Well, you see the array is in sorted order and the number that is before the number present at the right the position will be lesser, therefore if we sum this lesser number with the number present at the left position, we will get a lower sum that will move towards the value of the target.
If the number present at left and the number present at right positions add up to less than what the target is, we increase the left pointer. How? As we saw in the previous explanation, the array is in sorted order, and the number that is after the number present at the left of the position will be greater, therefore if we sum this greater number with the number present at the right position, we will get a greater sum that will move towards the value of the target.
If the number present at left and the number present at right positions add up to the value of the target, we simply return the pair of numbers that are present at the left and right positions respectively.

JavaScript Implementation of Two Sum Problem

Here is a simple JavaScript implementation of the two-pointer approach we discussed in the previous section:

Using Two Sum Approach to Implement Search Functionality

Before we start discussing the code, let’s have a look at what we are trying to achieve. Imagine you have delivered a blog based web application. Now your manager/client asks you to implement a search functionality in your web application that will enable users to search through the blogs by the keyword that they enter in the search bar. Understood? Great! Let’s jump in!

First, you need to create an array of blogs. We are creating this array statically for illustration purposes, however, you can fetch the same from databases such as firestore as well. In the article Using Merge K Sorted Lists Algorithm to Query Firestore Databases, I have written a piece of code that allows you to fetch data from Firestore collections, feel free to check that out! Each item in our array should have two keys title and content. Here is a sample array to get you started:

const blogs = [
  { title: 'JavaScript Basics', content: 'This blog covers the basics of JavaScript programming. },
  { title: 'React vs Vue', content: 'This blog compares React and Vue frameworks.' },
  { title: 'CSS Tricks', content: 'This blog shows CSS tricks.' },
  { title: 'Node.js Tutorial', content: 'This blog tells how to use Node.js' }
];
Code language: JavaScript (javascript)

Create a new function, name it searchBlogByKeyword()

function searchBlogByKeyword(){
   // we will write code here
}
Code language: JavaScript (javascript)

In the <body> tag of your index.html file, add the code written below:

<input type="text" id="search" placeholder="Search by blog title...">
<button onclick="searchBlogByKeyword()">Search</button>
<p id="blogTitle"></p>
<p id="blogDesc"></p>
Code language: HTML, XML (xml)

Now in your script.js file, target the input tag, the blogTitle paragraph and the blogDesc paragraph.

const keyword = document.getElementById('search').value.toLowerCase();
const blogTitle = document.getElementById('blogTitle');
const blogDesc = document.getElementById('blogDesc');
Code language: JavaScript (javascript)

Use the two-pointer approach discussed above, to find the blog title that contains the keyword searched:

let left = 0;
let right = keyword.length - 1;

while (left < keyword.length) {
   let substr = '';
   for (let i = left; i <= right; i++) {
      substr += keyword[i];
    }
   const result = blogs.findIndex(blog => blog.title.toLowerCase().includes(substr));
   if (result !== -1) {
     const title = blogs[result].title;
     const content = blogs[result].content;
     blogTitle.innerHTML = title;
     blogDesc.innerHTML = content;
     return;
    }
   left++;
   right++;
  }
  alert(`No blog found with title "${keyword}"`);
Code language: JavaScript (javascript)

I will now break down the code that we have written in the simplest possible manner:

First, we have initialized two pointers, the left pointer corresponds to the first letter of the keyword which is supposed to be searched and the right pointer corresponds to the last letter of the same keyword. These are the two detectives that will work together to crack our case (find our blog).
Next, we have configured the while loop to run for as long as the left pointer is at a position that does not exceed the length of the keyword, i.e., the loop will run for the entire keyword.
This is the most important step to look at – for each iteration, we are creating a “substring” using the left and right pointers. The pointer detectives are now using their magnifying glasses and zooming into specific parts of the keyword.
We now search for this substring in the title of each blog present in the blogs array. We have used the findIndex() method to perform this operation.
If the blog is found, its title and content are displayed on the page. If it isn’t then we increment the left and right pointers to look through another substring.
If the while loop completes and there is no blog found, we display an alert that says “No blog found with title keyword“.

Try this code in the playground yourself.
Note: Try searching CSS in the search box in the browser window.

Conclusion

In this article, we saw how a simple problem can help us solve a complex use case. I hope now you have a clear understanding of how things work under the hood and will never forget the two-pointer approach ever! Implementation of the two-pointer approach in a search bar for a blog was just one of the infinite use cases. I urge the readers to think more upon where this problem can be applied and comment below.

So, what are you waiting for? Go ahead and give the Two Pointer approach a try in your next web project. And while you are at it, you can go check out Codedamn’s Pro subscription for leveling up your web development skills even further while you write code in-browser and share with everyone using the playgrounds!

Happy learning!

Frequently Asked Questions

What is the two-sum problem in JavaScript?

The two-sum problem in JavaScript is a classic algorithmic problem that involves finding two numbers in an array that add up to a specific target value. It’s like trying to find two puzzle pieces that fit together perfectly to complete a picture. Using JavaScript, you can solve this problem using various approaches such as the Two Pointer method, the Hash Table method, and the Brute Force method. Each approach has its own advantages and disadvantages, but all of them are essential tools for any developer’s toolkit.

Can you make a search engine with JavaScript?

Absolutely! With the power of JavaScript, you can create a search engine that allows users to quickly and easily find the content they need. It’s like having a librarian who can find any book in the library within seconds. Using JavaScript, you can implement various search algorithms such as the Two Pointer method, Binary Search, and Linear Search to make your search engine fast and efficient.

What is Search() in JavaScript?

The Search() method in JavaScript is a built-in function that allows you to search for a specified substring within a string. It’s like a detective looking for a specific clue in a case file. The Search() method returns the index of the first occurrence of the substring, or -1 if the substring is not found. You can use the Search() method to implement search functionality in your web applications, but keep in mind that it only returns the index of the first occurrence of the substring, so you may need to use other methods like Regular Expressions to implement more advanced search features.

Can JavaScript control browser functionality?

Yes, JavaScript can control browser functionality! In fact, JavaScript is the primary language used for adding interactivity and dynamic functionality to web pages. With JavaScript, you can manipulate the DOM to add or remove elements from a web page, modify CSS styles, and even control browser events like clicks and scrolls. It’s like having a magic wand that can transform any webpage into a personalized work of art. Additionally, JavaScript can interact with browser APIs like localStorage, sessionStorage, and cookies to store and retrieve data, making your web applications more robust and user-friendly. So go ahead and unleash the power of JavaScript to control the browser and create amazing web experiences!