DEV Community: Emmanuel Ayinde

[Boost]

Emmanuel Ayinde — Thu, 01 Jan 2026 11:26:06 +0000

Gergely Orosz

Dec 1 '20

Six Principles Your Resume Should Follow - So Recruiters Will Read It

#books #career #beginners #resume

322

Comments 10

9 min read

Cracking Quick Sort algorithm: From Theory to Practice in Minutes

Emmanuel Ayinde — Wed, 06 Nov 2024 21:23:05 +0000

Quicksort is one of the fastest sorting algorithms. It takes an array of values, chooses one of the values as the 'pivot' element, and moves the other values so that lower values are on the left of the pivot element, and higher values are on the right of it.

Quick Sort stands as one of the most elegant and efficient sorting algorithms in the world of algorithms. Unlike simpler algorithms like Bubble Sort or Selection Sort, Quick Sort employs a sophisticated divide-and-conquer strategy that makes it significantly faster in practice. While Merge Sort also uses divide-and-conquer, Quick Sort's unique partitioning approach often leads to better performance and memory usage.

Average Time Complexity: O(n log n)

Worst Case Time Complexity: O(n²)

Space Complexity: O(log n)

What is quick sort algorithm
How does quick sort work
- Time Complexity
- Space Complexity
JavaScript Implementation
Conclusion

What is Quick Sort Algorithm

Quick Sort is a highly efficient sorting algorithm that works by selecting a 'pivot' element from the array and partitioning the other elements into two sub-arrays according to whether they are less than or greater than the pivot. Unlike Merge Sort, which divides first and combines later, Quick Sort does its sorting during the partitioning process.

Consider this comparison with other sorting algorithms:

Algorithm	Time Complexity (Average)	Space Complexity	In-Place?
Quick Sort	O(n log n)	O(log n)	Yes
Merge Sort	O(n log n)	O(n)	No
Bubble Sort	O(n²)	O(1)	Yes
Selection Sort	O(n²)	O(1)	Yes
Heap Sort	O(n log n)	O(1)	Yes

How does quick sort work?

Before we dive into the JavaScript implementation of quick sort algorithms, let's take a step-by-step approach to understand how the algorithm works by manually sorting a simple array of numbers with just four simple steps.

Quick sort can be broken down into four simple steps:

Choose a pivot element from the array. This element could be the first, the last, the middle or even a random element from the list/array.

Rearrange the array so that all elements less than the pivot are on the left, and all elements greater are on the right.

Swap the pivot element with the first element of the greater values, so that the pivot is in the middle.

Recursively apply the same operations to the sub-arrays on the left and right of the pivot.

Let's apply these steps to a real array. Shall we?

Initial Array: [3, 6, 2, 7, 1]

Step 1: Choose a Pivot

We choose the last element as the pivot for simplicity.
Pivot = 1

Step 2: Rearrange Array Around Pivot

Rearrange so that all elements less than the pivot (1) are on the left and all elements greater are on the right.
As we go through each element:
- 3 (greater than 1) → stays on the right.
- 6 (greater than 1) → stays on the right.
- 2 (greater than 1) → stays on the right.
- 7 (greater than 1) → stays on the right.
Rearranged Array: [1, 6, 2, 7, 3]

Step 3: Swap Pivot to its Correct Position

Swap the pivot (1) with the first element greater than it, which is 6.
Array after swapping: [1, 3, 2, 7, 6]
Now, 1 is in the correct position (index 0).

Step 4: Recursive Quick Sort on Sub-arrays

Left Sub-array: [] (no elements left of 1, so nothing to sort here)
Right Sub-array: [3, 2, 7, 6]

Sorting the Right Sub-array `[3, 2, 7, 6]` recursively

Step 1: Choose a Pivot

Pivot = 6 (last element)

Step 2: Rearrange Array Around Pivot

Arrange elements less than 6 to the left and greater ones to the right:
- 3 (less than 6) → stays on the left.
- 2 (less than 6) → stays on the left.
- 7 (greater than 6) → stays on the right.
Rearranged Array: [3, 2, 6, 7]

Step 3: Swap Pivot to Its Correct Position

6 is already in the correct position (index 2).
Array: [1, 3, 2, 6, 7]

Step 4: Recursive Quick Sort on Sub-arrays

Left Sub-array: [3, 2]
Right Sub-array: [7] (single element, no sorting needed)

Sorting the Left Sub-array `[3, 2]`

Step 1: Choose a Pivot

Pivot = 2 (last element)

Step 2: Rearrange Array Around Pivot

Rearrange so elements less than 2 are on the left:
- 3 (greater than 2) → stays on the right.
Rearranged Array: [2, 3]

Step 3: Swap Pivot to Its Correct Position

2 is already in the correct position (index 1).
Array: [1, 2, 3, 6, 7]

Step 4: Recursive Quick Sort on Sub-arrays

Left Sub-array: [] (no elements)
Right Sub-array: [3] (single element, no sorting needed)

Final Sorted Array

After sorting all the sub-arrays, we get the final sorted array:

Sorted Array: [1, 2, 3, 6, 7]

Below is the best illustration of how this works in real life:

Time Complexity

Quick Sort's time complexity varies based on pivot selection:

Best Case (O(n log n)):
- Occurs when the pivot always divides the array into equal halves
- Similar to Merge Sort's performance
Average Case (O(n log n)):
- Most practical scenarios
- Better than Merge Sort due to better cache utilization
Worst Case (O(n²)):
- Occurs with already sorted arrays and poor pivot selection
- Can be avoided with good pivot selection strategies

Space Complexity

Quick Sort's space complexity is O(log n) due to:

Recursive call stack depth
In-place partitioning (unlike Merge Sort's O(n) extra space)
Better memory efficiency compared to Merge Sort

JavaScript Implementation

function quickSort(arr) {
  // Base case: arrays with length 0 or 1 are already sorted
  if (arr.length <= 1) return arr;

  // Helper function to swap elements
  const swap = (i, j) => {
    [arr[i], arr[j]] = [arr[j], arr[i]];
  };

  // Partition function using Lomuto's partition scheme
  function partition(low, high) {
    const pivot = arr[high];
    let i = low - 1;

    for (let j = low; j < high; j++) {
      if (arr[j] <= pivot) {
        i++;
        swap(i, j);
      }
    }
    swap(i + 1, high);
    return i + 1;
  }

  // Main quickSort function implementation
  function quickSortHelper(low, high) {
    if (low < high) {
      const pivotIndex = partition(low, high);
      quickSortHelper(low, pivotIndex - 1); // Sort left side
      quickSortHelper(pivotIndex + 1, high); // Sort right side
    }
  }

  quickSortHelper(0, arr.length - 1);
  return arr;
}

Conclusion

Quick Sort is a popular choice due to its efficiency and in-place sorting. It outperforms simpler algorithms like Bubble Sort and Selection Sort with its O(n log n) average-case performance and low space complexity.

Key takeaways:

Choose pivot selection strategy carefully
Consider input characteristics when deciding between Quick Sort and other algorithms
Use randomized pivot selection for better average-case performance

Stay Updated and Connected

To ensure you don't miss any part of this series and to connect with me for more in-depth
discussions on Software Development (Web, Server, Mobile or Scraping / Automation), data
structures and algorithms, and other exciting tech topics, follow me on:

Emmanuel Ayinde Follow

Lead Full-Stack Software Engineer | Backend & AI Systems | Building Scalable, Production-Ready Products

Stay tuned and happy coding 👨‍💻🚀

Understanding merge sort algorithm: Beginner's guide to mastering sorting algorithm

Emmanuel Ayinde — Mon, 04 Nov 2024 22:42:08 +0000

In our previous articles, we've learned about quite a number of sorting algorithms like Bubble Sort, Selection Sort as well as Insertion Sort. We've learned that while these sorting algorithms are very easy to implement, they are not efficient for large datasets, which means we need a more efficient algorithm to handle sorting large datasets, hence merge sort. In this series, we'll go through how merge sort works and how it can be implemented in JavaScript. You ready?

What is Merge Sort Algorithm?
How Merge Sort Algorithms Works
- Time Complexity
- Space Complexity
Implementation in JavaScript
Conclusion

What is Merge Sort Algorithm?

Merge Sort Algorithm is an excellent sorting algorithm that follows the divide-and-conquer principle. Unlike simpler algorithms like Selection Sort and Bubble Sort that make multiple passes through the array comparing adjacent elements, Merge Sort takes a more strategic approach:

Divide: firstly, merge sort split the array into two halves
Conquer: secondly, it recursively sort each half
Combine: lastly, it merges the sorted halves back together

This approach consistently outperforms simpler O(n²) algorithms like Selection Sort and Bubble Sort when dealing with larger datasets.

How Merge Sort Algorithms Works

We've seen that merge sort works by using the popular divide-and-conquer approach. Below is a visual representation of how it works.

Now that we'v seen the magic, let's walk through how merge sort algorithm works by manually sorting this array: [38, 27, 43, 3, 9, 82, 10] using the approach mentioned above.

Step 1: Dividing

The first step in merge sort is dividing the array into subarrays, and then dividing each subarray into subarrays, and the subarray into subarrays until we have just one item left in all the subarrays.

Step 2: Merging Back (Conquering)

The second step is to start sorting those subarrays from the ground up.

Time Complexity

Merge Sort achieves O(n log n) time complexity in all cases (best, average, and worst), making it more efficient than O(n²) algorithms for larger datasets.

Here's why:

Dividing: The array is divided log n times (each division cuts the size in half)
Merging: Each level of merging requires n operations
Total: n operations × log n levels = O(n log n)

Compare this to:

Bubble Sort: O(n²)
Selection Sort: O(n²)
Merge Sort: O(n log n)

For an array of 1,000 elements:

O(n²) ≈ 1,000,000 operations
O(n log n) ≈ 10,000 operations

Space Complexity

Merge Sort requires O(n) additional space to store the temporary arrays during merging. While this is more than the O(1) space needed by Bubble Sort or Selection Sort, the time efficiency usually makes this trade-off worthwhile in practice.

Implementation in JavaScript

// The Merge Helper Function
function merge(left, right) {
  const result = [];
  let leftIndex = 0;
  let rightIndex = 0;

  while (leftIndex < left.length && rightIndex < right.length) {
    if (left[leftIndex] <= right[rightIndex]) {
      result.push(left[leftIndex]);
      leftIndex++;
    } else {
      result.push(right[rightIndex]);
      rightIndex++;
    }
  }

  // Add remaining elements
  while (leftIndex < left.length) {
    result.push(left[leftIndex]);
    leftIndex++;
  }

  while (rightIndex < right.length) {
    result.push(right[rightIndex]);
    rightIndex++;
  }

  return result;
}

Breaking Down the Merge Function:

Function Setup:

   const result = [];
   let leftIndex = 0;
   let rightIndex = 0;

Creates an empty array to store merged results
Initializes pointers for both input arrays
Think of these pointers like fingers keeping track of where we are in each array

Main Merging Logic:

   while (leftIndex < left.length && rightIndex < right.length) {
     if (left[leftIndex] <= right[rightIndex]) {
       result.push(left[leftIndex]);
       leftIndex++;
     } else {
       result.push(right[rightIndex]);
       rightIndex++;
     }
   }

Compares elements from both arrays
Takes the smaller element and adds it to result
Moves the pointer forward in the array we took from
Like choosing the smaller of two cards when sorting a deck

Cleanup Phase:

   while (leftIndex < left.length) {
     result.push(left[leftIndex]);
     leftIndex++;
   }

Adds any remaining elements
Necessary because one array might be longer than the other
Like gathering the remaining cards after comparing

The Main Merge Sort Function

function mergeSort(arr) {
  // Base case
  if (arr.length <= 1) {
    return arr;
  }

  // Divide
  const middle = Math.floor(arr.length / 2);
  const left = arr.slice(0, middle);
  const right = arr.slice(middle);

  // Conquer and Combine
  return merge(mergeSort(left), mergeSort(right));
}

Breaking Down MergeSort:

Base Case:

   if (arr.length <= 1) {
     return arr;
   }

Handles arrays of length 0 or 1
These are already sorted by definition
Acts as our recursion stopping point

Division Phase:

   const middle = Math.floor(arr.length / 2);
   const left = arr.slice(0, middle);
   const right = arr.slice(middle);

Splits array into two halves
slice() creates new arrays without modifying original
Like cutting a deck of cards in half

Recursive Sorting and Merging:

   return merge(mergeSort(left), mergeSort(right));

Recursively sorts each half
Combines sorted halves using merge function
Like sorting smaller piles of cards before combining them

Example Walkthrough

Let's see how it sorts [38, 27, 43, 3]:

First Split:

   [38, 27, 43, 3]
   ↙           ↘
   [38, 27]    [43, 3]

Second Split:

   [38, 27]    [43, 3]
   ↙    ↘      ↙    ↘
   [38] [27]   [43] [3]

Merge Back:

   [38] [27]   [43] [3]
      ↘↙          ↘↙
   [27, 38]    [3, 43]
       ↘        ↙
    [3, 27, 38, 43]

Conclusion

Merge Sort stands out as a highly efficient sorting algorithm that consistently performs well on large datasets. While it requires additional space compared to simpler sorting algorithms, its O(n log n) time complexity makes it a go-to choice for many real-world applications where performance is crucial.

Key takeaways:

Uses divide-and-conquer strategy
O(n log n) time complexity in all cases
Requires O(n) additional space
Stable sorting algorithm
Excellent for large datasets

Stay Updated and Connected

Emmanuel Ayinde Follow

Lead Full-Stack Software Engineer | Backend & AI Systems | Building Scalable, Production-Ready Products

Stay tuned and happy coding 👨‍💻🚀

Mastering Selection Sort Algorithm like a PRO

Emmanuel Ayinde — Fri, 18 Oct 2024 22:53:34 +0000

As we've been talking about different sorting algorithms, today we'll be learning about the selection sort algorithm. A sorting algorithm that allows for the possible minimum amount of swaps in a memory-constrained environment.

Introduction
What is Selection Sort Algorithm?
How does selection sort work?
- Time Complexity
- Space Complexity
Implementation in JavaScript
Solving LeetCode Problems
Conclusion

Introduction

Selection sort is a simple yet effective sorting algorithm that works by repeatedly selecting the smallest (or largest) element from the unsorted portion of the list and moving it to the beginning (or end) of the sorted portion. This process is repeated until the entire list is sorted. In this article, we will delve into the details of the selection sort algorithm, its implementation in JavaScript, and its applications in solving real-world problems.

What is Selection Sort Algorithm?

Selection Sort algorithm is an in-place comparison sorting algorithm. It divides the input list into two parts:

The sorted portion at the left end
The unsorted portion at the right end

The algorithm repeatedly selects the smallest element from the unsorted portion and swaps it with the leftmost unsorted element, moving the boundary between the sorted and unsorted portions one element to the right.

How does selection sort work?

Let's walk through an example using the array [64, 25, 12, 22, 11]:

Initial array: [64, 25, 12, 22, 11]

Sorted portion: []
Unsorted portion: [64, 25, 12, 22, 11]

First pass:

Find minimum in unsorted portion: 11
Swap 11 with first unsorted element (64)
Result: [11, 25, 12, 22, 64]
Sorted portion: [11]
Unsorted portion: [25, 12, 22, 64]

Second pass:

Find minimum in unsorted portion: 12
Swap 12 with first unsorted element (25)
Result: [11, 12, 25, 22, 64]
Sorted portion: [11, 12]
Unsorted portion: [25, 22, 64]

Third pass:

Find minimum in unsorted portion: 22
Swap 22 with first unsorted element (25)
Result: [11, 12, 22, 25, 64]
Sorted portion: [11, 12, 22]
Unsorted portion: [25, 64]

Fourth pass:

Find minimum in unsorted portion: 25
25 is already in the correct position
Result: [11, 12, 22, 25, 64]
Sorted portion: [11, 12, 22, 25]
Unsorted portion: [64]

Final pass:
- Only one element left, it's automatically in the correct position
- Final result: [11, 12, 22, 25, 64]

The array is now fully sorted.

Time Complexity

Selection Sort has a time complexity of O(n^2) in all cases (best, average, and worst), where n is the number of elements in the array. This is because:

The outer loop runs n-1 times
For each iteration of the outer loop, the inner loop runs n-i-1 times (where i is the current iteration of the outer loop)

This results in approximately (n^2)/2 comparisons and n swaps, which simplifies to O(n^2).

Due to this quadratic time complexity, Selection Sort is not efficient for large datasets. However, its simplicity and the fact that it makes the minimum possible number of swaps can make it useful in certain situations, especially when auxiliary memory is limited.

Space Complexity

Selection Sort has a space complexity of O(1) because it sorts the array in-place. It only requires a constant amount of additional memory space regardless of the input size. This makes it memory-efficient, which can be advantageous in memory-constrained environments.

Implementation in JavaScript

Here's a JavaScript implementation of Selection Sort Algorithm:

function selectionSort(arr) {
  const n = arr.length;

  for (let i = 0; i < n - 1; i++) {
    let minIndex = i;

    // Find the minimum element in the unsorted portion
    for (let j = i + 1; j < n; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j;
      }
    }

    // Swap the found minimum element with the first unsorted element
    if (minIndex !== i) {
      [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
    }
  }

  return arr;
}

// Example usage
const unsortedArray = [64, 25, 12, 22, 11];
console.log("Unsorted array:", unsortedArray);
console.log("Sorted array:", selectionSort(unsortedArray));

Let's break down the code:

We define a function selectionSort that takes an array as input.
We iterate through the array with the outer loop (i), which represents the boundary between the sorted and unsorted portions.
For each iteration, we assume the first unsorted element is the minimum and store its index.
We then use an inner loop (j) to find the actual minimum element in the unsorted portion.
If we find a smaller element, we update minIndex.
After finding the minimum, we swap it with the first unsorted element if necessary.
We repeat this process until the entire array is sorted.

Solving LeetCode Problems

Let'solve one leetcode algorithm problem using selection sort algorithm. Shall we?

Problem: Sort An Array `[Medium]`

Problem: Given an array of integers nums, sort the array in ascending order and return it. You must solve the problem without using any built-in functions in O(nlog(n)) time complexity and with the smallest space complexity possible.

Approach:: To solve this problem, we can directly apply the Selection Sort algorithm. This involves iterating through the array, finding the smallest element in the unsorted portion, and swapping it with the first unsorted element. We repeat this process until the entire array is sorted.

Solution:

// This function sorts an array of integers in ascending order using the Selection Sort algorithm.
const sortArray = function (nums) {
  // Get the length of the input array.
  const n = nums.length;

  // Iterate through the array, starting from the first element.
  for (let i = 0; i < n - 1; i++) {
    // Initialize the index of the minimum element to the current element.
    let minIndex = i;

    // Find the minimum element in the unsorted portion of the array.
    for (let j = i + 1; j < n; j++) {
      if (nums[j] < nums[minIndex]) {
        // Update the minimum index if a smaller element is found.
        minIndex = j;
      }
    }

    // Swap the found minimum element with the first unsorted element if necessary.
    if (minIndex !== i) {
      [nums[i], nums[minIndex]] = [nums[minIndex], nums[i]];
    }
  }

  // Return the sorted array.
  return nums;
};

This solution directly applies the Selection Sort algorithm we implemented earlier. While it correctly solves the problem, it's worth noting that this solution may exceed the time limit for large inputs on LeetCode due to the O(n^2) time complexity of Selection Sort. The image below shows that the solution is correct but not efficient.

Conclusion

In conclusion, Selection Sort is a simple and intuitive sorting algorithm that serves as an excellent introduction to the world of sorting techniques. Its simplicity makes it easy to understand and implement, making it a valuable learning tool for beginners. However, due to its quadratic time complexity O(n^2), it is not efficient for large datasets. For larger datasets or performance-critical applications, more efficient algorithms like QuickSort, MergeSort, or built-in sorting functions are preferred.

Stay Updated and Connected

Emmanuel Ayinde Follow

Lead Full-Stack Software Engineer | Backend & AI Systems | Building Scalable, Production-Ready Products

Stay tuned and happy coding 👨‍💻🚀

Understanding insertion sort algorithm: Beginner's guide with leetcode problems

Emmanuel Ayinde — Thu, 17 Oct 2024 11:01:00 +0000

There are many sorting algorithms 🧮, and each has its own strengths and weaknesses. Some are more efficient for large datasets 📊, while others are simpler and easier to understand 🤓. In this article, we'll explore one of the simplest sorting algorithms, Insertion Sort 📥. We'll look at how it works, its algorithm complexity, and how to implement it in JavaScript and finally solve some LeetCode problems using Insertion Sort 🏆.

I hope you are ready for this? Are you?

Introduction
What is an Insertion Sort Algorithm?
How does Insertion Sort work?
- Time Complexity
- Space Complexity
Implementation of Insertion Sort
Solving LeetCode Problems
Conclusion
References

Introduction

Insertion Sort algorithm is a comparison-based sorting algorithm that builds a sorted array one element at a time. It is one of the simplest sorting algorithms and is also known as a stable sort algorithm. It can be used for sorting small data sets or for educational purposes and can be implemented with just a few lines of code.

What is an Insertion Sort Algorithm?

Insertion Sort is a simple sorting algorithm that builds the final sorted array one item at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort. However, it has advantages such as simple implementation, efficient for small data sets, stable sort, and in-place sorting algorithm.

How does Insertion Sort work?

Imagine we have an array [5, 3, 8, 4, 2] that we want to sort in ascending order using Insertion Sort. Here's how we'll go about it:

Start with [5] (first element is considered sorted)
Take 3: [5, 3] → [3, 5] (3 is smaller than 5, so we swap them)
Take 8: [3, 5, 8] (8 is already in the correct position)
Take 4: [3, 5, 8, 4] → [3, 4, 5, 8] (4 is smaller than 8, so we swap them)
Take 2: [3, 4, 5, 8, 2] → [2, 3, 4, 5, 8] (2 is smaller than 8, so we swap them)

Final sorted array: [2, 3, 4, 5, 8]

Time Complexity

Best-case scenario: O(n)
- Occurs when the array is already sorted
- The algorithm only needs to do n-1 comparisons
Average-case scenario: O(n^2)
- On average, each element must be compared with about half of the previous elements
Worst-case scenario: O(n^2)
- Occurs when the array is sorted in reverse order (that is, the array is in descending order and we want to sort it in ascending order)
- Each element must be compared with all previous elements

Space Complexity

Insertion Sort has a space complexity of O(1) because it sorts the array in-place. It only requires a constant amount of additional memory space regardless of the input size.

Implementation of Insertion Sort

Having understood how Insertion Sort works, let's implement it in JavaScript:

function insertionSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    let key = arr[i]; // current element
    let j = i - 1; // index of previous element

    // Move elements of arr[0...i-1] that are greater than key
    // to one position ahead of their current position
    while (j >= 0 && arr[j] > key) {
      arr[j + 1] = arr[j];
      j = j - 1;
    }
    arr[j + 1] = key;
  }
  return arr;
}

console.log(insertionSort([5, 3, 8, 4, 2])); // Output: [2, 3, 4, 5, 8]

Let's break down the code:

We start with the second element (index 1 from our for-loop) because we consider the first element as already sorted.
We store the current element as key.
We compare key with the elements before it, moving elements that are greater than key one position ahead.
We place key in its correct position in the sorted portion of the array.
We repeat this process for all elements in the array.

It is important to note that Insertion Sort is already optimal for small data sets and mostly sorted arrays. However, it becomes inefficient for large, unsorted arrays. In such cases, more advanced algorithms like QuickSort or MergeSort are preferred.

Solving LeetCode Problems

Let's look at a LeetCode problem that can be solved using Insertion Sort:

Problem 1: Sort an Array `[Easy]`

Problem: You are given two integer arrays nums1 and nums2, sorted in non-decreasing order, and two integers m and n, representing the number of elements in nums1 and nums2 respectively.

Merge nums1 and nums2 into a single array sorted in non-decreasing order.

The final sorted array should not be returned by the function, but instead be stored inside the array nums1. To accommodate this, nums1 has a length of m + n, where the first m elements denote the elements that should be merged, and the last n elements are set to 0 and should be ignored. nums2 has a length of n.

Approach: We can use a for-loop to traverse the array and insert each element into the correct position in the sorted portion. This is a direct application of insertion sort.

Solution:

function merge(nums1, m, nums2, n) {
  // Step 1: Copy elements from nums2 into nums1
  for (let i = 0; i < n; i++) {
    nums1[m + i] = nums2[i];
  }
  // Step 2: Apply Insertion Sort on the merged nums1 array
  for (let i = 1; i < m + n; i++) {
    let key = nums1[i];
    let j = i - 1;

    // Shift elements of nums1[0..i-1] that are greater than key to one position ahead
    while (j >= 0 && nums1[j] > key) {
      nums1[j + 1] = nums1[j];
      j--;
    }
    nums1[j + 1] = key; // Insert key at the correct position
  }
}

Problem 2: Insertion Sort List `[Medium]`

Problem: Given the head of a singly linked list, sort the list using insertion sort, and return the sorted list's head.

Approach: This problem is a direct application of insertion sort. We can use a dummy node to keep track of the sorted portion of the list and insert each node into the correct position in the sorted portion. We can use a pointer to traverse the list and insert each node into the correct position in the sorted portion.

Solution:

// Function to perform insertion sort on a linked list
const insertionSortList = function (head) {
  // Create a dummy node to simplify insertion at the beginning
  let dummy = new ListNode(0);
  let current = head;

  // Iterate through each node in the original list
  while (current) {
    // Start from the dummy node to find the correct position
    let prev = dummy;

    // Move prev until we find the right position to insert current
    while (prev.next && prev.next.val < current.val) {
      prev = prev.next;
    }

    // Store the next node to process
    let next = current.next;

    // Insert current node into the sorted portion
    current.next = prev.next;
    prev.next = current;

    // Move to the next unsorted node
    current = next;
  }

  // Return the head of the sorted list (excluding dummy node)
  return dummy.next;
};

Noticed how we used while-loop to traverse the list and insert each node into the correct position in the sorted portion. Unlike the array implementation of insertion sort where we used for-loop to traverse the array and insert each element into the correct position in the sorted portion. This is because our data structure is a linked list and not the regular array.

Conclusion

Insertion Sort is a very simple and straightforward sorting algorithm that's especially effective for small arrays or arrays that are already mostly sorted. While it may not be the most efficient choice for large, unsorted datasets, its simplicity makes it a great starting point for understanding sorting algorithms.

Key takeaways:

Insertion Sort builds the final sorted array one item at a time.
It's efficient for small datasets and nearly-sorted arrays.
It has a best-case time complexity of O(n) and a worst-case of O(n^2).
It sorts in-place, requiring only O(1) additional memory.

Understanding Insertion Sort provides a solid foundation for learning more complex sorting algorithms and helps in solving various coding problems efficiently.

References

Stay Updated and Connected

Emmanuel Ayinde Follow

Lead Full-Stack Software Engineer | Backend & AI Systems | Building Scalable, Production-Ready Products

Stay tuned and happy coding 👨‍💻🚀

Understanding bubble sort algorithm: Beginner's guide with leetcode problems

Emmanuel Ayinde — Wed, 16 Oct 2024 07:33:23 +0000

In the world of programming, sorting algorithms are fundamental. They're used in various applications, from organizing data in databases to optimizing search functions. Bubble Sort, with its straightforward approach, serves as a stepping stone to understanding more advanced sorting techniques.

Introduction
What is Bubble Sort?
How does Bubble Sort work?
- Time Complexity
- Space Complexity
Implementation of Bubble Sort
Optimizing Bubble Sort
Solving LeetCode Bubble Sort Problems
Conclusion

Introduction

Bubble Sort is one of the simplest sorting algorithms, making it an excellent starting point for our journey in sorting techniques. While it may not be the most efficient for large datasets, understanding Bubble Sort lays a solid foundation for understanding more complex sorting algorithms.

What is Bubble Sort?

Bubble Sort is a simple sorting algorithm that repeatedly steps through a list, compares adjacent elements, and swaps them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted.

Bubble sort sort elements basically by comparing each pair of elements in the array and swapping them if they are in the wrong order. It is an in-place sorting algorithm, meaning it sorts the elements within the array itself without needing additional memory.

The algorithm gets its name from the way smaller elements "bubble" to the top of the list with each iteration, similar to air bubbles rising in a liquid.

How does Bubble Sort work?

Before we start writing code, let's walk through how Bubble Sort works using an example array: [5, 3, 8, 4, 2]. Assume we have this array [5, 3, 8, 4, 2] and we want to sort it in ascending order using Bubble Sort.

First pass:

Compare 5 and 3: Swap → [3, 5, 8, 4, 2]
Compare 5 and 8: No swap
Compare 8 and 4: Swap → [3, 5, 4, 8, 2]
Compare 8 and 2: Swap → [3, 5, 4, 2, 8]

Second pass:

Compare 3 and 5: No swap
Compare 5 and 4: Swap → [3, 4, 5, 2, 8]
Compare 5 and 2: Swap → [3, 4, 2, 5, 8]
Compare 5 and 8: No swap

Third pass:

Compare 3 and 4: No swap
Compare 4 and 2: Swap → [3, 2, 4, 5, 8]
Compare 4 and 5: No swap
Compare 5 and 8: No swap

Fourth pass:

Compare 3 and 2: Swap → [2, 3, 4, 5, 8]
Compare 3 and 4: No swap
Compare 4 and 5: No swap
Compare 5 and 8: No swap

Fifth pass:
- No swaps needed, the array is sorted

After each pass, the largest unsorted element "bubbles up" to its correct position at the end of the array. Notice how the number of total passes is 5 which is the length of the array but the last pass has no swap whatsoever, meaning if we had used 5 - 1 = 4 as the total number of passes, we'd have gotten the correct result. This is because the last element is already in its correct position after the fourth pass.

Time and Space Complexity of Bubble Sort

It is important to note that Bubble Sort is not the most efficient sorting algorithm for large datasets due to its quadratic time complexity O(n^2). However, it is still a good algorithm for small datasets or for educational purposes.

Time Complexity

The time complexity of Bubble Sort can be analyzed in three scenarios:

Worst-case scenario: O(n^2)

This occurs when the array is in reverse order (meaning the array is already sorted in descending order and we want to sort it in ascending order), requiring the maximum number of swaps.
For each of the n elements, we potentially need to do n-1 comparisons.

Best-case scenario: O(n)

This occurs when the array is already sorted.
With optimization (stopping early if no swaps are made), we only need to do one pass through the array.

Average-case scenario: O(n^2)
- On average, we can expect quadratic time complexity.

Here, n represents the number of elements in the array.

Space Complexity

Bubble Sort has a space complexity of O(1), which means it uses constant extra space.

This is because Bubble Sort is an in-place sorting algorithm. It doesn't require any extra array or data structure for sorting. The swaps are done within the original array, using only a constant amount of extra memory for variables (like loop counters and temporary variables for swapping).

Implementation of Bubble Sort

We've seen how Bubble Sort works and how to analyze its time and space complexity, let's now implement it in JavaScript.

Here's a basic implementation of Bubble Sort in JavaScript:

function bubbleSort(arr) {
  const n = arr.length;

  for (let i = 0; i < n - 1; i++) {
    // <--- Outer loop runs n-1 times (O(n))
    for (let j = 0; j < n - i - 1; j++) {
      // <--- Inner loop runs n-1 times (O(n))
      if (arr[j] > arr[j + 1]) {
        // Swap elements
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
      }
    }
  }

  return arr;
}

// Example usage:
const unsortedArray = [64, 34, 25, 12, 22, 11, 90];
console.log("Unsorted array:", unsortedArray); // [64, 34, 25, 12, 22, 11, 90]
console.log("Sorted array:", bubbleSort(unsortedArray)); // [11, 12, 22, 25, 34, 64, 90]

Let's break down the code:

The outer loop for (let i = 0; i < n - 1; i++) runs n-1 times, where n is the length of the array. This is because the last element is already in its correct position after the (n-1)th pass.
The inner loop for (let j = 0; j < n - i - 1; j++) compares adjacent elements (arr[j] and arr[j + 1]). Notice how the loop decreases as we progress through the array (i.e n - i - 1). This expression means that after you've looped through a number of elements from the first loop (i.e i from the outer loop), the number of comparisons decreases by i, so in our inner loop, we'd be comparing n - i - 1 elements not n - 1.
If an element is greater than the next one, they are swapped using destructuring assignment.
This process continues until no more swaps are needed.

Optimizing Bubble Sort

We can optimize Bubble Sort by adding a flag to check if any swaps were made in a pass. If no swaps were made, it means the array is already sorted, and we can stop the algorithm early.

Here's the optimized version:

function optimizedBubbleSort(arr) {
  const n = arr.length;
  let swapped;

  for (let i = 0; i < n - 1; i++) {
    swapped = false; // We initialize swapped to false

    for (let j = 0; j < n - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        // Swap elements
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
        swapped = true; // We set swapped to true to indicate that a swap occurred
      }
    }

    // If no swapping occurred, this means the array is sorted
    if (!swapped) break; // We break out of the loop if no swaps occurred
  }

  return arr;
}

// Example usage:
const unsortedArray = [64, 34, 25, 12, 22, 11, 90];
console.log("Unsorted array:", unsortedArray); // [64, 34, 25, 12, 22, 11, 90]
console.log("Sorted array:", optimizedBubbleSort(unsortedArray)); // [11, 12, 22, 25, 34, 64, 90]

This optimization improves the best-case time complexity to O(n) when the array is already sorted or nearly sorted.

Solving LeetCode Bubble Sort Problems

Having studied how bubble sort works and how to implement it, let's solve some LeetCode problems using bubble sort to solidify our understanding.

Problem 1: Maximum Product of Two Elements in an Array `[Easy]`

Problem: Given the array of integers nums, you will choose two different indices i and j of that array. Return the maximum value of (nums[i]-1)*(nums[j]-1).

Approach: This problem is a direct application of bubble sort. We can sort the array in ascending order and return the product of the last two elements, which are the two largest elements in the array.

Solution:

const maxProduct = function (nums) {
  // Implement bubble sort
  for (let i = 0; i < nums.length - 1; i++) {
    let swapped = false;
    for (let j = 0; j < nums.length - i - 1; j++) {
      if (nums[j] > nums[j + 1]) {
        // Swap elements
        [nums[j], nums[j + 1]] = [nums[j + 1], nums[j]];
        swapped = true;
      }
    }
    // If no swapping occurred, array is sorted
    if (!swapped) break;
  }

  // Return the product of the last two elements (largest two)
  return (nums[nums.length - 1] - 1) * (nums[nums.length - 2] - 1);
};

Problem 2: Sort Colors `[Medium]`

Problem: Given an array nums with n objects colored red, white, or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white, and blue. We will use the integers 0, 1, and 2 to represent the color red, white, and blue, respectively. You must solve this problem without using the library's sort function.

Approach: We can use bubble sort to solve this problem efficiently. Since we only have three distinct values (0, 1, and 2), we can sort the array in-place using bubble sort. The algorithm will compare adjacent elements and swap them if they are in the wrong order. After each pass, the largest unsorted element will "bubble up" to its correct position. We'll repeat this process until the entire array is sorted, resulting in all red elements (0) at the beginning, followed by white elements (1), and then blue elements (2) at the end.

Solution:

const sortColors = function (nums) {
  var len = nums.length;
  for (var i = 0; i < len - 1; i++) {
    for (var j = 0; j < len - 1 - i; j++) {
      if (nums[j] > nums[j + 1]) {
        // Swap nums[j] and nums[j + 1]
        var temp = nums[j];
        nums[j] = nums[j + 1];
        nums[j + 1] = temp;
      }
    }
  }
  return nums;
};

Conclusion

Bubble Sort is a simple and intuitive sorting algorithm that serves as an excellent introduction to the world of sorting techniques. Its simplicity makes it easy to understand and implement, making it a valuable learning tool for beginners.

Key points to remember about Bubble Sort:

It repeatedly steps through the list, comparing adjacent elements and swapping them if they're in the wrong order.
The algorithm gets its name from the way smaller elements "bubble" to the top of the list with each iteration.
Time complexity: Worst and Average case O(n^2), Best case O(n) with optimization.
Space complexity: O(1) as it sorts in-place.
It can be optimized to stop early if the list becomes sorted before all passes are complete.

While Bubble Sort is not efficient for large datasets due to its quadratic time complexity O(n^2), understanding it provides a solid foundation for learning more advanced sorting algorithms. In practice, for larger datasets or performance-critical applications, more efficient algorithms like QuickSort, MergeSort, or built-in sorting functions are preferred.

In our next article, we'll be learning about another sorting algorithm called Selection Sort.

Stay Updated and Connected

Emmanuel Ayinde Follow

Lead Full-Stack Software Engineer | Backend & AI Systems | Building Scalable, Production-Ready Products

Stay tuned and happy coding 👨‍💻🚀

Mastering Time and Space Complexity: A Beginner's Guide to Big O Notation

Emmanuel Ayinde — Mon, 14 Oct 2024 20:58:10 +0000

In your journey to becoming a proficient software or data engineer, understanding algorithm complexity is crucial. It helps you make informed decisions about the efficiency of your code and ensures that your applications perform well even as the data grows.

In this article, we'll explore the concept of algorithm complexity, specifically focusing on time and space complexity and how to calculate them using Big O notation.

Introduction
What is Algorithm Complexity?
- Time Complexity
- Space Complexity
Asymptotic Notation
How to Calculate Complexity
- How to Calculate Time Complexity
- How to Calculate Space Complexity
Common Runtime Complexities
Conclusion

Introduction

If you've ever been tasked with optimizing code, you've likely encountered the concept of algorithm complexity. At its core, complexity deals with the efficiency of an algorithm, focusing on how much time and space it requires to run as the input size grows.

What is Algorithm Complexity?

Algorithm complexity refers to the amount of time and space required by an algorithm to complete its execution. It helps us understand how efficient an algorithm is and how it scales with the size of the input data.

Time Complexity

Time complexity measures how the runtime of an algorithm increases with the size of the input. It answers the question: "As we add more data, how much longer will our algorithm take?"

It is a measure of how much time an algorithm takes to complete its execution as a function of the input size. It helps us understand the performance of an algorithm in terms of time.

Space Complexity

Space complexity measures how much additional memory an algorithm needs as the input size grows. It answers the question: "As we add more data, how much more memory will our algorithm use?"

It is a measure of how much memory an algorithm uses as a function of the input size. It helps us understand the performance of an algorithm in terms of memory.

Sometimes, you might prioritize one over the other. For instance:

In a mobile app with limited memory, you might prioritize space efficiency.
In a real-time system where quick responses are crucial, time efficiency might be more important.

Asymptotic Notation## Asymptotic Notation

When discussing algorithmic complexity, we use asymptotic notation to describe how the runtime or space usage grows as the input size approaches infinity. There are three main notations:

Big O Notation (O)

Represents the upper bound or worst-case scenario
Example: O(n) means the algorithm will never be slower than linear time

Big Omega Notation (Ω)

Represents the lower bound or best-case scenario
Example: Ω(log n) means the algorithm will never be faster than logarithmic time

Big Theta Notation (Θ)
- Represents both upper and lower bounds or average-case scenario
- Example: Θ(n) means the algorithm is always linear time

How to Calculate Complexity

Calculating complexity involves analyzing how the number of operations grows with the input size. It involves counting the number of operations and expressing them in terms of the input size (usually n).

How to calculate time complexity

To calculate the time complexity, we can follow these steps:

Count the number of operations (primitive operations)
Express the number of operations in terms of the input size (usually n)
Keep only the highest order term (the term with the largest growth rate)
Drop constants

NOTE 🔥

The steps above can also be applied to space complexity excepts we are dealing with memory which means we are counting the number of variables and the size of the input data instead of the number of operations.

Take for example we have the following function:

function sumArray(arr) {
  let sum = 0; // 1 operation
  for (let i = 0; i < arr.length; i++) {
    // n operations (where n is the array length)
    sum += arr[i]; // n operations (where n is the array length)
  }
  return sum; // 1 operation
}

In this example, the function sumArray takes an array arr as input and returns the sum of its elements. Let's analyze the complexity following the steps we mentioned earlier:

Step 1: Count the number of operations

Initialization: let sum = 0; - 1 operation
Loop: for (let i = 0; i < arr.length; i++) - n operations (where n is the length of the array, i.e n = arr.length)
Summation: sum += arr[i]; - n operations
Return: return sum; - 1 operation

So, the total number of operations is 1 + n + n + 1 = 2n + 2.

Step 2: Express the number of operations in terms of the input size (usually n)

The total number of operations is 2n + 2.

Step 3: Keep only the highest order term (the term with the largest growth rate)
From our expression 2n + 2, the highest order term is 2n. So we keep 2n.

Step 4: Drop constants
From 2n, we drop the constant 2. So we are left with n.

So, the time complexity of the sumArray function is O(n).

NOTE: As n approaches infinity (meaning, as n gets larger and larger says 1000, 10000, 100000, etc.), the constant 2 becomes insignificant, so we can simplify the complexity to O(n).

How to calculate space complexity

When it comes to space complexity, we are interested in the amount of memory used by the algorithm as a function of the input size.

We usually use this formular to calculate space complexity:

Space Complexity Formular

Space Complexity = Auxiliary space + Input size

NOTE 🔥

Auxiliary space is the extra or temporary space (excluding input size) used by the algorithm while Input size is the space taken by the input data.

For any algorithm, memory is required for the following:

To store program instructions
To store constant values
To store variables
To handle function calls, jumping statements, etc.

Let's look at an example to understand this better.

function sumArray(arr) {
  let sum = 0; // i unit of space
  for (let i = 0; i < arr.length; i++) {
    // n operations (where n is the array length)
    sum += arr[i]; // n operations (where n is the array length)
  }
  return sum; // 1 operation
}

from the above function, we have the following:

Auxiliary space: 0
Input size: n

So, the space complexity is O(n).

In the context of algorithm complexity, primitive operations refer to the basic operations that a computer can perform in a single step. These operations are typically simple and fundamental, such as:

Arithmetic operations: Addition, subtraction, multiplication, and division.

Variable assignments: Assigning a value to a variable.

Comparisons: Checking if one value is greater than, less than, or equal to another.

Logical operations: Operations like AND (&&), OR (||), and NOT (!).

Array access: Accessing an element in an array by its index.

When analyzing the time complexity of an algorithm, we count these primitive operations to estimate how the runtime of the algorithm grows as the size of the input increases. This helps in understanding the efficiency of the algorithm.

Common Runtime Complexities

Finally before we go, let's look at some common runtime complexities with their respective code implementations:

Common Runtimes

Here are some common time complexities you'll encounter:

1. Constant time - O(1)

Runtime doesn't increase with input size
Example: Accessing an array element by index

Code Implementation

function getFirstElement(arr) {
  return arr[0];
}

Illustration

2. Logarithmic time - O(log n)

Runtime increases logarithmically with input size
Example: Binary search

Code Implementation

function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;
  while (left <= right) {
    let mid = Math.floor((left + right) / 2);
    if (arr[mid] === target) return mid;
    if (arr[mid] < target) left = mid + 1;
    else right = mid - 1;
  }
  return -1;
}

Illustration

3. Linear time - O(n)

Runtime increases linearly with input size
Example: Linear search

Code Implementation

function linearSearch(arr, target) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === target) return i;
  }
  return -1;
}

Illustration

4. Polynomial time - O(n^k)

Runtime is a polynomial function of input size
Example: Nested loops

Code Implementation

function printPairs(arr) {
  for (let i = 0; i < arr.length; i++) {
    for (let j = 0; j < arr.length; j++) {
      console.log(arr[i], arr[j]);
    }
  }
}

5. Exponential time - O(2^n)

Runtime doubles with each addition to the input
Example: Recursive Fibonacci

Code Implementation

function fibonacci(n) {
  if (n <= 1) return n;
  return fibonacci(n - 1) + fibonacci(n - 2);
}

6. Factorial time - O(n!)

Runtime grows factorial with input size
Example: Generating all permutations

Code Implementation

function generatePermutations(arr) {
  if (arr.length <= 1) return [arr];
  let result = [];
  for (let i = 0; i < arr.length; i++) {
    let rest = [...arr.slice(0, i), ...arr.slice(i + 1)];
    let perms = generatePermutations(rest);
    result.push(...perms.map((perm) => [arr[i], ...perm]));
  }
  return result;
}

Conclusion

In this article, we've explored the concept of algorithm complexity, specifically focusing on time and space complexity and how to calculate them using Big O notation. We've also looked at how to calculate the space complexity of an algorithm.

In our next article, we'll be focusing on sorting algorithms, their implementations and their complexities.Until then,

Stay Updated and Connected

Stay tuned and happy coding 👨‍💻🚀

Hash Tables Demystified: The Ultimate Guide with JavaScript Implementation

Emmanuel Ayinde — Sat, 12 Oct 2024 22:36:49 +0000

Imagine you're in a vast library with millions of books 📚. How do you find the exact book you're looking for without spending hours searching through every shelf? 🕵️‍♀️ The answer lies in the library's catalog system - a powerful tool that allows you to locate any book in seconds ⚡. This is precisely the real-world analogy of a Hash Table, a fundamental data structure that enables lightning-fast data storage and retrieval 🚀.

Hi 👋, welcome to this article on Hash Tables! In this article, we'll be demystifying Hash Tables 🧩, exploring their inner workings and implementing them in JavaScript.

Before we move on, let's take a look at what we'll be covering in this article:

Introduction
What is a Hash Table?
Common Terminologies Used in Hash Tables
How Hash Tables Work
Implementing a Hash Table in JavaScript
- Creating the Hash Table
- Adding Values to the Hash Table
- Retrieving Values from the Hash Table
- Removing Values from the Hash Table
- Checking if a Value exists in the Hash Table
Conclusion

Introduction

The importance of Hash Tables in the world of programming cannot be overstated. They are the backbone of many real-world applications, from database indexing to caching systems, and from compilers to blockchain technology. Moreover, Hash Tables are a favorite topic in coding interviews, making them an essential skill for any aspiring software developer.

You might be wondering why we need a Hash Table in the first place. A Hash Table is a data structure designed to be fast to work with.

The reason Hash Tables are sometimes preferred instead of arrays or linked lists is because searching for, adding, and deleting data can be done really quickly, even for large amounts of data.

In a Linked List, finding a person "Esther" takes time because we would have to go from one node to the next, checking each node, until the node with "Esther" is found.

And finding "Esther" in an Array could be fast if we knew the index, but when we only know the name "Esther", we need to compare each element (like with Linked Lists), and that takes time.

With a Hash Table however, finding "Esther" is done really fast because there is a way to go directly to where "Esther" is stored, using something called a hash function.

In this comprehensive article, we'll demystify Hash Tables, explore their inner workings, implement them in JavaScript, and solve popular LeetCode problems. By the end of this journey, you'll have a solid understanding of Hash Tables and be well-equipped to optimize your code and ace your next coding interview.

That being said, let's dive into the world of Hash Tables!

What is a Hash Table?

A hash table is a data structure that allows you to store data in key-value pairs and quickly access it using a key. Think of it like a dictionary or a phone book, where you can look up information (value) by a name (key). A hash table is a data structure that stores values using keys. It uses a hash function to compute an index into an array in which an element will be stored.

Common Terminologies Used in Hash Tables

Term	Definition
Key	The identifier used to store or retrieve a value in the hash table.
Value	The actual data associated with the key.
Hash Function	A function that converts the key into a unique hash code used to store the value.
Bucket / Slot	A location in the hash table where a value is stored, indexed by the hash code.
Collision	When two different keys produce the same hash code and are assigned to the same bucket.
Chaining	A method for handling collisions by storing multiple values in a list within a bucket.
Rehashing	Resizing the hash table and recalculating hash codes to redistribute the keys.
Hash Code	The result of the hash function used as the index to store or retrieve values.

How Hash Tables Work

Again, let use the analogy of a vast library of books to get key insight into how Hash Table works. Think of a hash table like a library where you want to store books on shelves, but instead of just throwing them anywhere, you use a clever way of organizing them.

Here’s how it works step-by-step:

Step 1: Hashing is Like Labeling the Book
When you have a book, you need to figure out where to place it in the library. You don’t just choose a random shelf. Instead, you calculate the shelf number based on the book’s title.

This is where the hash function comes in. A hash function is like a special librarian that looks at the title of a book (like the key in a hash table) and decides which shelf the book should go on (like the index in an array). For example:

Title: "Alice in Wonderland"
The librarian (hash function) checks the title and decides: "Put it on Shelf 3." It calculates a shelf number based on the title in a consistent way, so every time you bring "Alice in Wonderland," it will always tell you to use Shelf 3.

Step 2: Storing the Book (Key-Value Pair)
In a hash table, each shelf is actually a bucket. When you know the shelf number (from the hash function), you place the book (value) on that shelf.

You store the book (value) along with its title (key) on the shelf.
This key-value relationship ensures that you can easily find the book later.
For example:
Shelf 3 (bucket) now contains:
- "Alice in Wonderland" → 555-1234 (phone number)

Step 3: Retrieving a Book (Getting a Value)
Let’s say you want to find the phone number for "Alice in Wonderland". The hash table process works as follows:

You go to the librarian (hash function) and ask, "Where is 'Alice in Wonderland'?"
The librarian calculates the same shelf number: Shelf 3.
You walk over to Shelf 3 and find the book, which has the phone number 555-1234. This is the efficiency of a hash table: It doesn't need to search every shelf; it knows exactly where to look!

Step 4: Handling Collisions (Multiple Books on One Shelf)
Sometimes, two books may end up on the same shelf (because of the way the hash function works). This is called a collision.

For example:

"Alice in Wonderland" and "Anna Karenina" might both be placed on Shelf 3. When you retrieve a book from Shelf 3, you might have multiple books there, so you just look through the few that are on that shelf. This is why buckets sometimes contain more than one key-value pair.

This structure is highly efficient and is used for fast data retrieval in many applications, such as dictionaries and databases.

Implementing a Hash Table in JavaScript

Let's roll up our sleeves and implement a simple Hash Table in JavaScript. We'll go through this process step-by-step, explaining each part of the implementation.

When it comes to implementing a Hash Table, the first thing we need to do is to create a hash function. This hash function will take a key and return an index in the array where the value should be stored. To implement this, we'll use a simple algorithm that involves multiplying by a prime number and taking the modulo with the array length.

A hash map uses a simple array (or a list of buckets) to store data. The data is accessed by using a key and the hash function maps that key to an index in the array.

Hash Map: We'll represent the hash map as an array.
Hash Function: This will take a string key, convert it into a hash code (an index in the array), and return that index. The hash function needs to ensure that keys are mapped to valid indices within the array bounds.

Let's start by creating our Hash Map class and the hash function:

Creating the Hash Table

// Hash Map class
class HashTable {
  constructor(size) {
    this.size = size; // size of the hash map (number of buckets)
    this.buckets = new Array(size); // create an array of the given size (buckets)
  }

  // Hash function to generate an index based on the key
  _hash(key) {
    let hashValue = 0;
    for (let i = 0; i < key.length; i++) {
      hashValue += key.charCodeAt(i); // get the ASCII value () of each character and sum it
    }
    return hashValue % this.size; // ensure the index is within the bounds of the array
  }
}

// Create a hash map of size 10 and test the hash function
let myHashTable = new HashTable(10);
console.log(myHashTable._hash("Alice")); // This will return the index for "Alice"
console.log(myHashTable._hash("Bob")); // This will return the index for "Bob"

Explanation:

We created a HashTable class with a size and an array of buckets (empty spots).
The hash function (_hash) takes a key, sums up the ASCII values of the characters, and modulo the result by the size of the array to ensure the result stays within the array’s bounds.
This function is private (indicated by _) because we don't want it to be directly accessible outside the class.

ASCII, which stands for American Standard Code for Information Interchange, is a character encoding standard used to represent text in computers and other devices that use text. It is a 7-bit code, meaning it uses seven bits to represent a character, allowing for 128 possible characters (0-127). The ASCII table includes control characters (0-31 and 127), printable characters (32-126), and extended ASCII characters (128-255).

Now that we can generate an index from a key, the next step is to insert values into the hash table. We'll create a function called set that:

Adding Values to the Hash Table

Now that we can generate an index from a key, the next step is to insert values into the hash map. We'll create a function called set that:

Takes a key-value pair.
Uses the hash function to find the index (bucket) where the value should be stored.
Adds the key-value pair into that bucket. We will use chaining (a list at each bucket) to handle potential collisions (when two keys map to the same bucket).

// Add values to the hash map

set(key, value) {
  const index = this._hash(key); // Get the index for the key

  // Initialize the bucket if it's empty
  if (!this.buckets[index]) {
    this.buckets[index] = []; // Use an array to handle multiple values (chaining)
  }

  // Add the key-value pair to the bucket
  this.buckets[index].push([key, value]);
  console.log(`Set ${key}: ${value} at index ${index}`);
}

// Example of adding values
myHashMap.set("Alice", "555-1234");
myHashMap.set("Bob", "555-5678");
myHashTable.set("Charlie", "555-9999");

Explanation:

The set method uses the hash function to find the correct index.
If the bucket at that index is empty, it initializes an empty list.
The key-value pair is then pushed into that bucket.
This implementation handles collisions by chaining—storing multiple key-value pairs in a list if two keys map to the same bucket.

Retrieving Values from the Hash Table

Once we've inserted values, the next logical step is to retrieve values. We'll create a function get that:

Takes a key.
Uses the hash function to find the index (bucket) where the value should be stored.
Searches the bucket for the key and returns the value if found.

// Retrieve values from the hash map

get(key) {
  const index = this._hash(key); // Get the index for the key

  // Check if the bucket at that index exists
  if (!this.buckets[index]) {
    return null; // If the bucket is empty, return null (key not found)
  }

  // Search through the bucket for the key
  for (let i = 0; i < this.buckets[index].length; i++) {
    const pair = this.buckets[index][i];
    if (pair[0] === key) {
      return pair[1]; // Return the value if the key is found
    }
  }

  return null; // Return null if the key is not found in the bucket
}

// Example of retrieving values
console.log(myHashMap.get("Alice"));   // Should print "555-1234"
console.log(myHashMap.get("Bob"));     // Should print "555-5678"
console.log(myHashMap.get("Charlie")); // Should print "555-9999"
console.log(myHashMap.get("Dave"));    // Should print null (not found)

Explanation:

The get function finds the index for the key using the hash function.
If the bucket at that index is empty, it returns null because the key doesn't exist.
If there are multiple entries in that bucket (due to collisions), the function searches through the list to find the correct key and returns its value.

Removing Values from the Hash Table

To complete the basic operations of a hash table, we'll add a method to remove a key-value pair. This function will:

Take a key.
Use the hash function to find the bucket.
Remove the key-value pair if found.

// Remove values from the hash map

// Remove values from the hash map
remove(key) {
  const index = this._hash(key); // Get the index for the key

  // Check if the bucket exists
  if (!this.buckets[index]) {
    return null; // If the bucket is empty, return null (key not found)
  }

  // Search through the bucket for the key
  for (let i = 0; i < this.buckets[index].length; i++) {
    const pair = this.buckets[index][i];
    if (pair[0] === key) {
      this.buckets[index].splice(i, 1); // Remove the key-value pair from the bucket
      return pair[1]; // Return the removed value
    }
  }

  return null; // Return null if the key is not found in the bucket
}

// Example of removing values
console.log(myHashMap.remove("Alice"));   // Should print "555-1234"
console.log(myHashMap.get("Alice"));      // Should now print null (not found)

Explanation:

The remove function searches for the key in the appropriate bucket and removes the key-value pair if found.
After removal, it returns the value that was removed.
If the key doesn't exist, it returns null.

Checking if a Value exists in the Hash Table

The contains function will:

Loop through all the buckets in the hash map.
Check each key-value pair in the bucket.
Return true if the value is found, and false if it's not.

// Check if the hash map contains a specific value
contains(value) {
  // Loop through all the buckets
  for (let i = 0; i < this.size; i++) {
    const bucket = this.buckets[i];

    // If the bucket exists, search through its key-value pairs
    if (bucket) {
      for (let j = 0; j < bucket.length; j++) {
        const pair = bucket[j];
        if (pair[1] === value) { // Check if the value matches
          return true; // Return true if the value is found
        }
      }
    }
  }

  return false; // Return false if the value is not found in any bucket
}

// Example of checking for values
console.log(myHashMap.contains("555-1234")); // Should return false (because Alice was removed)
console.log(myHashMap.contains("555-5678")); // Should return true (Bob's number)
console.log(myHashMap.contains("555-9999")); // Should return true (Charlie's number)
console.log(myHashMap.contains("555-8888")); // Should return false (not found)

Explanation:

The contains function loops through each bucket in the hash map.
If the bucket exists (i.e., it contains some key-value pairs), it checks whether any value in that bucket matches the value we are looking for.
If it finds a match, it returns true; otherwise, after searching all buckets, it returns false.

Conclusion

Hash Tables are a powerful and versatile data structure that offer efficient data storage and retrieval. Through this guide, we've explored their inner workings, implemented them in JavaScript, and solved several LeetCode problems that leverage their strengths.

In our next article, we'll be solving some LeetCode problems that use Hash Tables. Until then, happy coding!

Stay Updated and Connected

To ensure you don't miss any part of this series and to connect with me for more in-depth discussions on Software Development (Web, Server, Mobile or Scraping / Automation), data structures and algorithms, and other exciting tech topics, follow me on:

Stay tuned and happy coding 👨‍💻🚀

Cracking Stack and Queue LeetCode Problems: A Step-by-Step Guide to Solving LeetCode Challenges

Emmanuel Ayinde — Thu, 10 Oct 2024 22:30:12 +0000

Learning how to use stacks and queues effectively is an important skill for any developer, and it's a common topic in coding interviews 🎯. In this article, we'll go over some LeetCode problems that involve the use of stacks and queues, and we'll solve them using JavaScript 💻.

Welcome back to this new article in the DSA series 📚! If you've been following my articles up till last article, you'll notice that I've been going over the basic concepts of stacks and queues, how they work and the terminologies used when talking about them 🧠.

Introduction
Problem 1: Implement Stack using Queues
Problem 2: Implement Queue using Stacks
Problem 3: Valid Parentheses
Problem 4: Decode String
Conclusion

Introduction

In the last two articles, we've gone over the basic concepts of stacks and queues 📚, how they work and the terminologies used when talking about them as well as their implementations in JavaScript. In this article, we'll be solving some problems on LeetCode that involves the use of stacks and queues using our implementations. Get ready to put your knowledge to the test and level up your coding skills! 🚀

Before we start cracking some problems, let's quickly remind ourselves the basic of queue and stack.

Stack: Think of a stack as a pile of books. You can only add or remove books from the top. Last In, First Out (LIFO).

For more information on stack, check out my previous article.

Understanding Stack Data Structure: A Step-by-Step Guide to Implementing Stack in JavaScript

Emmanuel Ayinde
Emmanuel Ayinde

Emmanuel Ayinde

Follow

Oct 8 '24

Understanding Stack Data Structure: A Step-by-Step Guide to Implementing Stack in JavaScript

#beginners #javascript #dsa #datastructures

5 reactions
Comments Add Comment

6 min read

Queue: Imagine a line at a ticket counter. The first person in line is the first to be served. First In, First Out (FIFO).

For more information on queue, check out my previous article.

Understanding Queues Data Structure: Mastering FIFO Principle in JavaScript

Emmanuel Ayinde
Emmanuel Ayinde

Emmanuel Ayinde

Follow

Oct 9 '24

Understanding Queues Data Structure: Mastering FIFO Principle in JavaScript

#beginners #javascript #dsa #programming

6 reactions
Comments Add Comment

5 min read

Now that we've refreshed our memories, let's go over some problems. Shall we?

Problem 1: Implement Stack using Queues

Problem Link: LeetCode - Implement Stack using Queues

Explanation:

We need to implement a stack using only queue operations. The main challenge is that queues follow FIFO, while stacks follow LIFO.

Approach:

We'll use two queues. When pushing an element, we'll add it to the first queue and then move all other elements behind it.

Solution:

class MyStack {
  constructor() {
    this.queue1 = [];
    this.queue2 = [];
  }

  push(x) {
    // Add the new element to queue2
    this.queue2.push(x);

    // Move all elements from queue1 to queue2
    while (this.queue1.length > 0) {
      this.queue2.push(this.queue1.shift());
    }

    // Swap queue1 and queue2
    [this.queue1, this.queue2] = [this.queue2, this.queue1];
  }

  pop() {
    return this.queue1.shift();
  }

  top() {
    return this.queue1[0];
  }

  empty() {
    return this.queue1.length === 0;
  }
}

Problem 2: Implement Queue using Stacks

Problem Link: LeetCode - Implement Queue using Stacks

Explanation:

We need to implement a queue using only stack operations. The challenge is to convert LIFO (stack) behavior to FIFO (queue) behavior.

Approach:

We'll use two stacks. One for enqueue operations and another for dequeue operations.

Solution:

class MyQueue {
  constructor() {
    this.stack1 = []; // For enqueue
    this.stack2 = []; // For dequeue
  }

  push(x) {
    this.stack1.push(x);
  }

  pop() {
    if (this.stack2.length === 0) {
      this.transferStack1ToStack2();
    }
    return this.stack2.pop();
  }

  peek() {
    if (this.stack2.length === 0) {
      this.transferStack1ToStack2();
    }
    return this.stack2[this.stack2.length - 1];
  }

  empty() {
    return this.stack1.length === 0 && this.stack2.length === 0;
  }

  transferStack1ToStack2() {
    while (this.stack1.length > 0) {
      this.stack2.push(this.stack1.pop());
    }
  }
}

Problem 3: Valid Parentheses

Problem Link: LeetCode - Valid Parentheses

Explanation:

We need to determine if the input string has valid parentheses, meaning every opening bracket must have a corresponding closing bracket in the correct order.

Approach:

We'll use a stack to keep track of opening brackets and check if they match with closing brackets.

Solution:

const isValid = (s) => {
  const stack = [];
  const bracketPairs = {
    ")": "(",
    "}": "{",
    "]": "[",
  };

  for (let char of s) {
    if (!bracketPairs[char]) {
      // It's an opening bracket, push to stack
      stack.push(char);
    } else {
      // It's a closing bracket
      if (stack.pop() !== bracketPairs[char]) {
        return false;
      }
    }
  }

  // If stack is empty, all brackets were matched
  return stack.length === 0;
};

Problem 4: Decode String

Problem Link: LeetCode - Decode String

Explanation:

We need to decode a string that contains repeated substrings enclosed in square brackets, preceded by a number indicating the repetition count.

Approach:

We'll use two stacks: one for numbers and another for characters. We'll build the decoded string piece by piece.

Solution:

const decodeString = (s) => {
  const numStack = [];
  const strStack = [];
  let currentNum = 0;
  let currentStr = "";

  for (let char of s) {
    if (char >= "0" && char <= "9") {
      currentNum = currentNum * 10 + parseInt(char);
    } else if (char === "[") {
      numStack.push(currentNum);
      strStack.push(currentStr);
      currentNum = 0;
      currentStr = "";
    } else if (char === "]") {
      let repeatTimes = numStack.pop();
      let prevStr = strStack.pop();
      currentStr = prevStr + currentStr.repeat(repeatTimes);
    } else {
      currentStr += char;
    }
  }

  return currentStr;
};

Conclusion

In this blog post, we've explored the fundamental concepts of Queues and Stacks and solved several LeetCode problems that showcase their implementation and use cases. By working through these problems, you've gained valuable insight into how these data structures can be applied to solve complex coding challenges.

Stay Updated and Connected

To ensure you don't miss any part of this series and to connect with me for more in-depth discussions on Software Development (Web, Server, Mobile or Scraping / Automation), data structures and algorithms, and other exciting tech topics, follow me on:

Stay tuned and happy coding 👨‍💻🚀

Understanding Queues Data Structure: Mastering FIFO Principle in JavaScript

Emmanuel Ayinde — Wed, 09 Oct 2024 22:57:20 +0000

Picture this... 🎬 Imagine you're at a busy coffee shop during the morning rush ☕️. As you enter, you see a long line of caffeine-craving customers waiting to place their orders. The baristas, working efficiently behind the counter, take and prepare orders in the exact sequence that people joined the line. This everyday scenario perfectly illustrates the concept of a Queue as a data structure.

In the world of programming, a Queue is a fundamental data structure that adheres to the First In, First Out (FIFO) principle. Just like the coffee shop line, the first person to join the queue is the first one to be served and leave it 🥇. This simple yet powerful concept has wide-ranging applications in various areas of computer science and software development, from managing print jobs 🖨️ and handling network requests 🌐 to implementing breadth-first search algorithms and coordinating task scheduling in operating systems 💻.

In this particular article, we'll explore the fascinating world of Queues, delving into their inner workings, implementations, and practical applications in JavaScript 🚀. Whether you're new to coding or an intermediate programmer looking to deepen your understanding, this tutorial will provide you with the knowledge and skills to effectively utilize the Queue data structure in your projects 🛠️.

What is a Queue?
Key Terminology
Types of Queues
Queue Operations
Real-World Applications of Queues
Queue Implementation in JavaScript
Conclusion

What is a Queue?

A Queue is a linear data structure that follows the First In, First Out (FIFO) principle. It can be visualized as a line of people waiting for a service, where the person who arrives first is served first. In programming terms, this means that the first element added to the queue will be the first one to be removed.

Key Terminology

Before we delve deeper into Queues, let's familiarize ourselves with some key terms:

Term	Description
Enqueue	The process of adding an element to the rear (end) of the queue.
Dequeue	The process of removing an element from the front of the queue.
Front	The first element in the queue, which will be the next to be removed.
Rear	The last element in the queue, where new elements are added.
IsEmpty	A condition that checks if the queue has no elements.
Size	The number of elements currently in the queue.

Types of Queues

While we'll primarily focus on the basic Queue implementation, it's worth noting that there are several types of Queues:

Simple Queue: The standard FIFO queue we'll be implementing.
Circular Queue: A queue where the rear is connected to the front, forming a circle. This is more memory efficient for fixed-size queues.
Priority Queue: A queue where elements have associated priorities, and higher priority elements are dequeued before lower priority ones.

Queue Operations

The main operations performed on a Queue are:

Enqueue: Add an element to the rear of the queue.
Dequeue: Remove and return the element at the front of the queue.
Peek: Return the element at the front of the queue without removing it.
IsEmpty: Check if the queue is empty.
Size: Get the number of elements in the queue.

Real-World Applications of Queues

Queues have numerous practical applications in computer science and software development:

Task Scheduling: Operating systems use queues to manage processes and tasks.
Breadth-First Search (BFS): In graph algorithms, queues are used to explore nodes level by level.
Print Job Spooling: Printer queues manage the order of print jobs.
Keyboard Buffer: Queues store keystrokes in the order they were pressed.
Web Servers: Request queues help manage incoming HTTP requests.
Asynchronous Data Transfer: Queues in messaging systems ensure data is processed in the correct order.

Queue Implementation in JavaScript

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

class Queue {
  constructor() {
    this.front = null;
    this.rear = null;
    this.size = 0;
  }

  // Add an element to the rear of the queue
  enqueue(value) {
    const newNode = new Node(value);
    if (this.isEmpty()) {
      this.front = newNode;
      this.rear = newNode;
    } else {
      this.rear.next = newNode;
      this.rear = newNode;
    }
    this.size++;
  }

  // Remove and return the element at the front of the queue
  dequeue() {
    if (this.isEmpty()) {
      return "Queue is empty";
    }
    const removedValue = this.front.value;
    this.front = this.front.next;
    this.size--;
    if (this.isEmpty()) {
      this.rear = null;
    }
    return removedValue;
  }

  // Return the element at the front of the queue without removing it
  peek() {
    if (this.isEmpty()) {
      return "Queue is empty";
    }
    return this.front.value;
  }

  // Check if the queue is empty
  isEmpty() {
    return this.size === 0;
  }

  // Return the number of elements in the queue
  getSize() {
    return this.size;
  }

  // Print the elements of the queue
  print() {
    if (this.isEmpty()) {
      console.log("Queue is empty");
      return;
    }
    let current = this.front;
    let queueString = "";
    while (current) {
      queueString += current.value + " -> ";
      current = current.next;
    }
    console.log(queueString.slice(0, -4)); // Remove the last " -> "
  }
}

// Usage example
const queue = new Queue();

queue.enqueue(10);
queue.enqueue(20);
queue.enqueue(30);

console.log("Queue after enqueuing 10, 20, and 30:");
queue.print(); // Output: 10 -> 20 -> 30

console.log("Front element:", queue.peek()); // Output: 10

console.log("Dequeued element:", queue.dequeue()); // Output: 10

console.log("Queue after dequeuing:");
queue.print(); // Output: 20 -> 30

console.log("Queue size:", queue.getSize()); // Output: 2

console.log("Is queue empty?", queue.isEmpty()); // Output: false

queue.enqueue(40);
console.log("Queue after enqueuing 40:");
queue.print(); // Output: 20 -> 30 -> 40

while (!queue.isEmpty()) {
  console.log("Dequeued:", queue.dequeue());
}

console.log("Is queue empty?", queue.isEmpty()); // Output: true

Conclusion

Congratulations! You've now mastered the Queue data structure in JavaScript. From understanding its basic principles to implementing various types of queues and solving LeetCode problems, you've gained a solid foundation in this essential computer science concept.

Queues are not just theoretical constructs; they have numerous real-world applications in software development, from managing asynchronous tasks to optimizing data flow in complex systems. As you continue your programming journey, you'll find that a deep understanding of queues will help you design more efficient algorithms and build more robust applications.

To further solidify your knowledge, I encourage you to practice more Queue-related problems on LeetCode and other coding platforms

Stay Updated and Connected

To ensure you don't miss any part of this series and to connect with me for more in-depth discussions on Software Development (Web, Server, Mobile or Scraping / Automation), data structures and algorithms, and other exciting tech topics, follow me on:

Stay tuned and happy coding 👨‍💻🚀

Understanding Stack Data Structure: A Step-by-Step Guide to Implementing Stack in JavaScript

Emmanuel Ayinde — Tue, 08 Oct 2024 22:52:27 +0000

A Stack is a simple linear data structure that works like a stack of plates 🍽️. It follows the Last In, First Out (LIFO) principle. Think of it as a pile of plates: you can only add or remove plates from the top of the pile.

For a better understanding of stack, let's embark on a short journey of imagination 🌟.
Imagine you're at a fancy restaurant 🍽️, and the kitchen staff is preparing for a busy night 👨‍🍳. In the dish area, there's a tall stack of plates waiting to be used. As diners arrive and orders pour in, the staff takes plates from the top of the stack. When clean plates are added, they go right on top. This simple system ensures that the plates at the bottom of the stack which have been there the longest are used last, while the freshly cleaned plates on top are used first ✨.

This, in essence, is how a Stack data structure works. A Stack is a linear data structure that follows the Last In First Out (LIFO) principle. Just like with our stack of plates, the last item added to a Stack is the first one to be removed.

In this comprehensive tutorial on the stack data structure, we'll explore the following topics with a simple, beginner-friendly approach:

What is a Stack?
Pros and Cons of Using Stack
Real-World Applications of Stacks
Key Operations on a Stack
Stack Implementation in JavaScript
Conclusion

Are you ready? Let's dive in

What is a Stack?

A Stack is a linear data structure that follows the Last In, First Out (LIFO) principle. This means that the last element added to the stack will be the first one to be removed. Think of it like a stack of books: you can only add or remove books from the top of the stack.

Pros and Cons of Using Stack

Before we continue with the flow and write some codes, it is great to understanding where and where not to use Stack. The table below give an explicit Pros and Cons of Stack in details.

Pros	Cons
Simple and easy to implement	Limited access (only top element is directly accessible)
Efficient for Last-In-First-Out (LIFO) operations	Not suitable for random access of elements
Constant time O(1) for push and pop operations	Can lead to stack overflow if not managed properly
Useful for tracking state in algorithms (e.g., depth-first search)	Not ideal for searching or accessing arbitrary elements
Helps in memory management (e.g., call stack in programming languages)	Fixed size in some implementations (array-based stacks)
Useful for reversing data	May require resizing in dynamic implementations, which can be costly
Supports recursive algorithms naturally	Not efficient for large datasets that require frequent traversal
Helps in expression evaluation and syntax parsing	Potential for underflow if pop operation is called on an empty stack
Useful in undo mechanisms in software	Limited functionality compared to more complex data structures
Efficient for certain types of data organization (e.g., browser history)	Not suitable for problems requiring queue-like (FIFO) behavior

Key Operations on a Stack

The fundamental operations that can be performed on a stack are:

push(): Adds an element to the top of the stack.
pop(): Removes the topmost element from the stack.
peek(): Returns the top element of the stack without removing it.
isEmpty(): Checks if the stack is empty.
size(): Returns the number of elements in the stack.

Real-World Applications of Stacks

Stacks are every where in computer science and software development. Here are some common applications:

Undo Functionality: In text editors or graphic design software, each action is pushed onto a stack. When you hit "undo," the most recent action is popped off the stack and reversed.
Browser History: When you visit a new page, it's pushed onto a stack. The "back" button pops the current page off the stack, revealing the previous one.
Function Call Stack: In programming languages, function calls are managed using a stack. When a function is called, it's pushed onto the call stack. When it returns, it's popped off.
Expression Evaluation: Stacks are used to evaluate arithmetic expressions, especially those in postfix notation.
Backtracking Algorithms: In problems like maze-solving or puzzle-solving, stacks can keep track of the path taken, allowing easy backtracking when needed.

Stack Implementation in JavaScript

Now, let's implement a Stack in JavaScript. It is important to know that there are different ways to implement a stack in JavaScript. One of the common ways to implement a stack is using array, another way is to use linked list. In this article, we'll implement a stack using linked list (singly linked list).

Implement Stack using Linked List

I hope you still remember how linked list works? You might need to check out the linked list implementation in one of our previous articles in this same series.

Emmanuel Ayinde

Oct 4 '24

How to Implement Singly Linked List in JavaScript

#javascript #beginners #programming #dsa

Comments

5 min read

Now, let's start implementing our stack using singly linked list. Shall we?

First, we'll create a Node class to represent our stack individual item.

class Node {
  constructor(data) {
    this.data = data;
    this.next = null;
  }
}

Then, we'll create a Stack class to represent our stack.

class Stack {
  constructor() {
    this.top = null;
    this.size = 0;
  }

  // Stack Operations will be implemented here 👇
}

Push Operation

The push operation adds a new element to the top of the stack. It creates a new StackNode, sets its next pointer to the current top, and then updates top to point to this new node. Finally, it increments the size.

  // Push element to the top of the stack
  push(element) {
    const newNode = new Node(element);
    newNode.next = this.top;
    this.top = newNode;
    this.size++;
  }

Pop Operation

The pop operation removes the topmost element from the stack. It first checks if the stack is empty. If it is, it returns an error message. Otherwise, it removes the top element, updates the top pointer to the next node, and decrements the size. Finally, it returns the removed element.

  // Remove and return the top element
  pop() {
    if (this.isEmpty()) {
      return "Stack is empty";
    }
    const poppedElement = this.top.data;
    this.top = this.top.next;
    this.size--;
    return poppedElement;
  }

Peek Operation

The peek operation returns the top element without removing it. It first checks if the stack is empty. If it is, it returns an error message. Otherwise, it returns the data of the top element.

  // Return the top element without removing it
  peek() {
    if (this.isEmpty()) {
      return "Stack is empty";
    }
    return this.top.data;
  }

isEmpty Operation

The isEmpty operation checks if the stack is empty. It returns true if the stack is empty, and false otherwise.

  // Check if the stack is empty
  isEmpty() {
    return this.size === 0;
  }

getSize Operation

The getSize operation returns the size of the stack. It returns the number of elements in the stack.

  // Return the size of the stack
  getSize() {
    return this.size;
  }

Print Operation

The print operation prints the stack. It returns the data of the top element.

  // Print the stack
  print() {
    let current = this.top;
    let result = "";
    while (current) {
      result += current.data + " ";
      current = current.next;
    }
    console.log(result.trim());
  }

Usage Example

// Usage example
const customStack = new CustomStack();
customStack.push(10);
customStack.push(20);
customStack.push(30);
console.log(customStack.pop()); // 30
console.log(customStack.peek()); // 20
console.log(customStack.getSize()); // 2
console.log(customStack.isEmpty()); // false
customStack.print(); // 20 10

In this implementation, we used a linked list (singly linked list) structure to represent our stack. Each element is a Node with a data value and a reference to the next Node. The top of the stack is always the most recently added Node.

Conclusion

Stacks are a fundamental data structure in computer science that follow the Last In, First Out (LIFO) principle. They are used in various applications, including managing function calls, implementing undo functionality, and evaluating arithmetic expressions.

In this tutorial, we've covered the basics of stacks, pros and cons of using them, and their implementation in JavaScript (using linked list). Understanding stacks is not just about knowing how to implement them, but also recognizing when they're the right tool for solving a problem.

As you continue your journey in software development, you'll find that stacks are an indispensable tool in your problem-solving toolkit. They're simple yet powerful, and mastering them will significantly enhance your ability to design efficient algorithms and data structures.

Stay Updated and Connected

To ensure you don't miss any part of this series and to connect with me for more in-depth discussions on Software Development (Web, Server, Mobile or Scraping / Automation), data structures and algorithms, and other exciting tech topics, follow me on:

Stay tuned and happy coding 👨‍💻🚀

Linked List Mastery: Cracking LeetCode Problems on List

Emmanuel Ayinde — Mon, 07 Oct 2024 22:54:04 +0000

Hey 👋🏻, I know it's been a while since we embarked on this journey and I want to believe it has been an awesome one! 🚀

Today, we will be solving some of the most common linked list problems on LeetCode. 🧩 The idea is to get you familiar with the concept of linked lists and how to solve problems on them. 💡 The problems we will be tackling will cut across different types of linked lists, with difficulty ranging from easy to hard, all approached step by step. 📈 So, if you've been following this series, then you're good to go! 🎉 If not, you might want to check out the previous articles in this series to catch up. 📚

Emmanuel Ayinde

Oct 3 '24

Master Linked List like a Pro: Understanding how linked list works

#javascript #beginners #dsa #programming

Comments 1

7 min read

Emmanuel Ayinde

Oct 4 '24

How to Implement Singly Linked List in JavaScript

#javascript #beginners #programming #dsa

Comments

5 min read

Emmanuel Ayinde

Oct 5 '24

Master How Doubly Linked List is implemented in JavaScript

#javascript #beginners #programming #dsa

Comments 1

6 min read

Emmanuel Ayinde

Oct 6 '24

Circular Linked Lists Demystified: From Novice to Node Master

#javascript #beginners #programming #dsa

Comments

8 min read

Course Outline

Introduction
Linked List Problem-Solving Approach
Singly Linked List Problems
- Question 1: Reverse Linked List
- Question 2: Remove Nth Node From End of List
Conclusion

Introduction

In our last four articles, we have been through the concept of linked list and how to implement them in javascript. We started with the basic singly linked list and then moved on to doubly linked list and circular linked list (Where we also dealt with both singly and doubly circular linked list). In this article, we will be solving some of the most common linked list problems on leetcode from easy to hard across different types of linked list.

Linked List Problem-Solving Approach

When it comes to solving linked list problems, there are certain steps we can follow to ensure we get the correct answer. These steps are:

Understand the Problem:

Read the problem statement carefully.
Identify the input and output.
Clarify any assumptions or constraints.

Consider Edge Cases:

Think about what happens if the linked list is empty.
Consider the case where the linked list has only one node (the head).

Plan the Solution:

Think about the steps needed to solve the problem.
Consider using pointers or iteration to traverse the linked list (if needed).
Consider using a dummy node to simplify edge cases (if needed).

Implement the Solution:

Write the code to solve the problem.

Test the Solution:

Test the solution with different inputs to ensure it works correctly.
Check for any edge cases that were not considered.

Optimize the Solution:
- Consider the time complexity of the solution.
- Look for ways to improve the solution (e.g., using a faster algorithm).

Unfortunately, we won't be dealing with the time complexity of the solution in this article since we are more concerned with the concept and how to solve the problem.

Singly Linked List Problems

Under this section, we will be solving just two of the most common singly linked list problems on leetcode. They are: Reverse Linked List and Merge Two Sorted Lists

Question 1: Reverse Linked List

Given the head of a singly linked list, reverse the list, and return the reversed list.

Example 1:

Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]

Example 2: > > Input: head = [1,2] > Output: [2,1]

Approach

Since we are dealing with a singly linked list, that means there is only a data and a pointer to the next node in a single node. Since we can't traverse the list in reverse, we need to reverse the direction of the list. We can do this by simply changing the direction of the next pointer of each node.

Solution Implementation

/** Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

function reverseList(head) {
  if (!head) return null;
  if (!head.next) return head;
  let node = null;
  while (head) {
    let currentNode = head.next;
    head.next = node;
    node = head;
    head = currentNode;
  }
  return node;
}

Question 2: Remove Nth Node From End of List

Given the head of a linked list, remove the nth node from the end of the list and return its head.

Example 1: > > Input: head = [1,2,3,4,5], n = 2
Output: [1,2,3,5]

Example 2: > Input: head = [1], n = 1
Output: []

Approach

Use two pointers: a fast pointer and a slow pointer.
Move the fast pointer n nodes ahead.
Move both pointers until the fast pointer reaches the end.
The slow pointer will now be at the node before the one to be removed.
Update the next pointer of the slow pointer to skip the nth node.
Return the head of the modified list.

Solution Implementation

const removeNthFromEnd = function (head, n) {
  // Create a dummy node to handle edge cases (e.g., removing the head)
  const newNode = new ListNode(0);
  newNode.next = head;
  let first = newNode;
  let second = newNode;

  // Move the first pointer n+1 steps ahead
  for (let i = 0; i <= n; i++) {
    first = first.next;
  }

  // Move both pointers until the first pointer reaches the end
  while (first !== null) {
    first = first.next;
    second = second.next;
  }

  // Remove the nth node by updating the next pointer
  second.next = second.next.next;

  // Return the head of the modified list (excluding the dummy node)
  return newNode.next;
};

Conclusion

In this article, we have solved some of the most common linked list problems on LeetCode 🧩. We started with the reverse linked list problem and then moved on to the remove nth node from end of list problem. We have seen how to approach these problems and how to solve them step by step 🚶‍♂️👣.

Remember that practice is key to mastering linked list problems 💪. Here is a linked list problems collection on LeetCode containing about 75 problems ranging from easy to hard 📚.

Up next... We'll dive into Queue and Stack data structures! 🏊‍♂️🔍

Stay Updated and Connected

Stay tuned and happy coding 👨‍💻🚀

DEV Community: Emmanuel Ayinde

[Boost]

Six Principles Your Resume Should Follow - So Recruiters Will Read It

Cracking Quick Sort algorithm: From Theory to Practice in Minutes

Table of Contents

What is Quick Sort Algorithm

How does quick sort work?

Quick sort can be broken down into four simple steps:

Step 1: Choose a Pivot

Step 2: Rearrange Array Around Pivot

Step 3: Swap Pivot to its Correct Position

Step 4: Recursive Quick Sort on Sub-arrays

Sorting the Right Sub-array [3, 2, 7, 6] recursively

Step 1: Choose a Pivot

Step 2: Rearrange Array Around Pivot

Step 3: Swap Pivot to Its Correct Position

Step 4: Recursive Quick Sort on Sub-arrays

Sorting the Left Sub-array [3, 2]

Step 1: Choose a Pivot

Step 2: Rearrange Array Around Pivot

Step 3: Swap Pivot to Its Correct Position

Step 4: Recursive Quick Sort on Sub-arrays

Final Sorted Array

Time Complexity

Space Complexity

JavaScript Implementation

Conclusion

Stay Updated and Connected

Emmanuel Ayinde Follow

Understanding merge sort algorithm: Beginner's guide to mastering sorting algorithm

Table of Contents

What is Merge Sort Algorithm?

How Merge Sort Algorithms Works

Step 1: Dividing

Step 2: Merging Back (Conquering)

Time Complexity

Space Complexity

Implementation in JavaScript

Breaking Down the Merge Function:

The Main Merge Sort Function

Breaking Down MergeSort:

Example Walkthrough

Conclusion

Stay Updated and Connected

Emmanuel Ayinde Follow

Mastering Selection Sort Algorithm like a PRO

Table of Contents

Introduction

What is Selection Sort Algorithm?

How does selection sort work?

Time Complexity

Space Complexity

Implementation in JavaScript

Solving LeetCode Problems

Problem: Sort An Array [Medium]

Conclusion

Stay Updated and Connected

Emmanuel Ayinde Follow

Understanding insertion sort algorithm: Beginner's guide with leetcode problems

Table of Contents

Introduction

What is an Insertion Sort Algorithm?

How does Insertion Sort work?

Time Complexity

Space Complexity

Implementation of Insertion Sort

Solving LeetCode Problems

Problem 1: Sort an Array [Easy]

Problem 2: Insertion Sort List [Medium]

Conclusion

References

Stay Updated and Connected

Emmanuel Ayinde Follow

Understanding bubble sort algorithm: Beginner's guide with leetcode problems

Table of Contents

Introduction

What is Bubble Sort?

How does Bubble Sort work?

Time and Space Complexity of Bubble Sort

Time Complexity

Sorting the Right Sub-array `[3, 2, 7, 6]` recursively

Sorting the Left Sub-array `[3, 2]`

Problem: Sort An Array `[Medium]`

Problem 1: Sort an Array `[Easy]`

Problem 2: Insertion Sort List `[Medium]`

Problem 1: Maximum Product of Two Elements in an Array `[Easy]`

Problem 2: Sort Colors `[Medium]`