Problem #1: Two Sum

The problem is to find two numbers in an array that add up to a given target number. We need to return the indices of these two numbers in any order. We can assume that there is only one valid solution, and we cannot use the same element twice.

To solve this problem, we can use a hash table to store the indices of each number in the input array. Then, for each number in the array, we can check if its complement (i.e., the number that adds up to the target with the current number) is already in the hash table. If it is, we return the indices of the two numbers.

The time complexity of this algorithm is O(n), as we only need to iterate through the array once, and each hash table lookup takes O(1) time. The space complexity is also O(n), as we need to store the indices of each number in the hash table.

Here are the steps taken to solve the problem:

1. Create an empty hash table.
2. Iterate through the input array, and for each number:
   1. Calculate its complement (i.e., target – number).
   2. Check if its complement is already in the hash table. If it is, return the indices of the current number and its complement.
   3. If its complement is not in the hash table, add the current number and its index to the hash table.
3. If no solution is found, return an empty array.

JavaScript Solution:

function twoSum(nums, target) {
  // Create an empty hash table.
  const indices = {};

  // Iterate through the input array.
  for (let i = 0; i < nums.length; i++) {
    const num = nums[i];
    // Calculate the complement of the current number.
    const complement = target - num;

    // Check if the complement is in the hash table.
    if (indices[complement] !== undefined) {
      // Return the indices of the current number and its complement.
      return [indices[complement], i];
    }

    // Add the current number and its index to the hash table.
    indices[num] = i;
  }

  // If no solution is found, return an empty array.
  return [];
}

// Example usage:
const nums = [2, 7, 11, 15];
const target = 9;
console.log(twoSum(nums, target));  // Output: [0, 1]

const nums2 = [3, 2, 4];
const target2 = 6;
console.log(twoSum(nums2, target2));  // Output: [1, 2]

const nums3 = [3, 3];
const target3 = 6;
console.log(twoSum(nums3, target3));  // Output: [0, 1]

Python Solution:

def twoSum(nums, target):
    # Create an empty hash table.
    indices = {}

    # Iterate through the input array.
    for i, num in enumerate(nums):
        # Calculate the complement of the current number.
        complement = target - num

        # Check if the complement is in the hash table.
        if complement in indices:
            # Return the indices of the current number and its complement.
            return [indices[complement], i]

        # Add the current number and its index to the hash table.
        indices[num] = i

    # If no solution is found, return an empty list.
    return []

# Example usage:
nums = [2, 7, 11, 15]
target = 9
print(twoSum(nums, target))  # Output: [0, 1]

nums2 = [3, 2, 4]
target2 = 6
print(twoSum(nums2, target2))  # Output: [1, 2]

nums3 = [3, 3]
target3 = 6
print(twoSum(nums3, target3))  # Output: [0, 1]

Problem #2: Add Two Numbers

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example:

Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Explanation: 342 + 465 = 807.

Steps to solve the problem:

1. Initialize a dummy node and a carry variable.
2. Iterate through the input lists until we reach the end of both lists.
3. Add the values of the nodes, if they exist, and the carry.
4. Calculate the new carry and the value of the current node.
5. Move to the next nodes and repeat steps 2-4.
6. If there’s a carry left at the end, add a new node with the carry value.
7. Return the result as the next of the dummy node.

Pseudocode:

initialize dummy, current, and carry
while l1 or l2:
sum = carry
if l1:
sum += l1.val
l1 = l1.next
if l2:
sum += l2.val
l2 = l2.next
carry = sum // 10
current.next = Node(sum % 10)
current = current.next
if carry:
current.next = Node(carry)
return dummy.next

JavaScript Solution:

function ListNode(val, next) {
    this.val = (val === undefined ? 0 : val);
    this.next = (next === undefined ? null : next);
}

var addTwoNumbers = function(l1, l2) {
    let dummy = new ListNode(); // Create a dummy node
    let current = dummy; // Set current node to dummy
    let carry = 0; // Initialize carry to 0

    while (l1 || l2) { // Iterate through the lists until the end of both
        let sum = carry; // Set sum to the value of carry
        if (l1) {
            sum += l1.val; // If l1 exists, add its value to sum
            l1 = l1.next; // Move to the next node in l1
        }
        if (l2) {
            sum += l2.val; // If l2 exists, add its value to sum
            l2 = l2.next; // Move to the next node in l2
        }
        carry = Math.floor(sum / 10); // Calculate new carry
        current.next = new ListNode(sum % 10); // Create a new node with the current digit
        current = current.next; // Move to the next node
    }

    if (carry) {
        current.next = new ListNode(carry); // If there's a carry left, create a new node with its value
    }

    return dummy.next; // Return the result as the next of the dummy node
};

Python Solution:

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def addTwoNumbers(l1, l2):
    dummy = ListNode() # Create a dummy node
    current = dummy # Set current node to dummy
    carry = 0 # Initialize carry to 0

    while l1 or l2: # Iterate through the lists until the end of both
        _sum = carry # Set sum to the value of carry
        if l1:
            _sum += l1.val # If l1 exists, add its value to sum
            l1 = l1.next # Move to the next node in l1
        if l2:
            _sum += l2.val # If l2 exists, add its value to sum
            l2 = l2.next # Move to the next node in l2
        carry = _sum // 10 # Calculate new carry
        current.next = ListNode(_sum % 10) # Create a new node with the current digit
        current = current.next # Move to the next node

    if carry:
        current.next = ListNode(carry) # If there's a carry left, create a new node with its value

    return dummy.next # Return the result as the next of the dummy node

Problem #3: Longest Substring Without Repeating Characters

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

Example:

Input: s = “abcabcbb”
Output: 3
Explanation: The answer is “abc”, with the length of 3.

we are given a string, and we need to find the longest contiguous substring without any repeating characters. The challenge is to do this efficiently without using a brute-force approach, which would involve checking all possible substrings.

To solve this problem, we’ll use the sliding window technique, which maintains a window of characters without any repeating characters. This technique involves two pointers, left and right, which traverse the string from left to right. We’ll also use a hashmap (or dictionary) to store the index of each character in the string.

As we iterate through the string with the right pointer, we’ll check if the current character is already in the hashmap and if its index is greater than or equal to the left pointer. If so, it means we’ve found a repeating character, and we need to update the left pointer to the next index after the repeating character’s index. This will ensure that our window only contains unique characters.

Then, we’ll update the hashmap with the new character index and calculate the maximum length of the substring found so far. By the end of the iteration, the maximum length variable will hold the length of the longest substring without repeating characters.

Steps to solve the problem:

1. Initialize a hashmap to store the index of characters.
2. Initialize two pointers, left and right, to iterate through the string.
3. Iterate through the string with the right pointer.
4. If a character is already in the hashmap and its index is greater than or equal to the left pointer, update the left pointer to the next index.
5. Update the hashmap with the new character index.
6. Update the maximum length of the substring.

Pseudocode:

initialize charIndexMap, left, maxLength
for right in range(0, len(s)):
if s[right] in charIndexMap and charIndexMap[s[right]] >= left:
left = charIndexMap[s[right]] + 1
charIndexMap[s[right]] = right
maxLength = max(maxLength, right – left + 1)
return maxLength

JavaScript Solution:

const lengthOfLongestSubstring = (s) => {
    let charIndexMap = new Map(); // Initialize a hashmap to store the index of characters
    let left = 0; // Initialize the left pointer
    let maxLength = 0; // Initialize the maximum length

    for (let right = 0; right < s.length; right++) { // Iterate through the string with the right pointer
        if (charIndexMap.has(s[right]) && charIndexMap.get(s[right]) >= left) {
            // If a character is already in the hashmap and its index is greater than or equal to the left pointer,
            // update the left pointer to the next index
            left = charIndexMap.get(s[right]) + 1;
        }
        charIndexMap.set(s[right], right); // Update the hashmap with the new character index
        maxLength = Math.max(maxLength, right - left + 1); // Update the maximum length of the substring
    }

    return maxLength;
};

Python Solution:

def length_of_longest_substring(s):
    char_index_map = {} # Initialize a hashmap to store the index of characters
    left = 0 # Initialize the left pointer
    max_length = 0 # Initialize the maximum length

    for right in range(len(s)): # Iterate through the string with the right pointer
        if s[right] in char_index_map and char_index_map[s[right]] >= left:
            # If a character is already in the hashmap and its index is greater than or equal to the left pointer,
            # update the left pointer to the next index
            left = char_index_map[s[right]] + 1
        char_index_map[s[right]] = right # Update the hashmap with the new character index
        max_length = max(max_length, right - left + 1) # Update the maximum length of the substring

    return max_length

Problem #4: Median of Two Sorted Arrays

Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.

Example:

Input: nums1 = [1,3], nums2 = [2]
Output: 2.0
Explanation: merged array = [1,2,3] and median is 2.

Given two sorted arrays, we need to find the median element(s) after merging them. The challenge is to do this in O(log(min(m, n))) time complexity, where m and n are the lengths of the two arrays. We’ll use a binary search on the smaller array to find the correct partition points that divide the combined array into two equal parts.

Steps to solve the problem:

1. Ensure that nums1 is the smaller array. If not, swap nums1 and nums2.
2. Find the partition points in both arrays such that the left half has the same number of elements as the right half.
3. Binary search on the smaller array to find the correct partition points.
4. Check the conditions for the correct partition and calculate the median based on the partition points.

Pseudocode:

if len(nums1) > len(nums2):
swap(nums1, nums2)

low, high, partition_x, partition_y = 0, len(nums1), 0, 0
total_length = len(nums1) + len(nums2)

while low <= high:
partition_x = (low + high) // 2
partition_y = (total_length + 1) // 2 – partition_x

max_left_x = nums1[partition_x – 1] if partition_x > 0 else -inf
min_right_x = nums1[partition_x] if partition_x < len(nums1) else inf

max_left_y = nums2[partition_y – 1] if partition_y > 0 else -inf
min_right_y = nums2[partition_y] if partition_y < len(nums2) else inf

if max_left_x <= min_right_y and max_left_y <= min_right_x:
if total_length % 2 == 0:
return (max(max_left_x, max_left_y) + min(min_right_x, min_right_y)) / 2
else:
return max(max_left_x, max_left_y)
elif max_left_x > min_right_y:
high = partition_x – 1
else:
low = partition_x + 1

return 0

JavaScript Solution:

const findMedianSortedArrays = (nums1, nums2) => {
    if (nums1.length > nums2.length) {
        [nums1, nums2] = [nums2, nums1]; // Ensure nums1 is the smaller array
    }

    let low = 0;
    let high = nums1.length;
    let totalLength = nums1.length + nums2.length;

    while (low <= high) {
        let partitionX = Math.floor((low + high) / 2); // Find the partition point in nums1
        let partitionY = Math.floor((totalLength + 1) / 2) - partitionX; // Find the partition point in nums2

        let maxLeftX = partitionX > 0 ? nums1[partitionX - 1] : -Infinity;
        let minRightX = partitionX < nums1.length ? nums1[partitionX] : Infinity;

        let maxLeftY = partitionY > 0 ? nums2[partitionY - 1] : -Infinity;
        let minRightY = partitionY < nums2.length ? nums2[partitionY] : Infinity;

        if (maxLeftX <= minRightY && maxLeftY <= minRightX) {
            // If the correct partition is found
            if (totalLength % 2 === 0) {
                return (Math.max(maxLeftX, maxLeftY) + Math.min(minRightX, minRightY)) / 2;
            } else {
                return Math.max(maxLeftX, maxLeftY);
            }
        } else if (maxLeftX > minRightY) {
            high = partitionX - 1;
        } else {
            low = partitionX + 1;
        }
    }

    return 0;
};

Python Solution:

import sys

def findMedianSortedArrays(nums1, nums2):
    if len(nums1) > len(nums2):
        nums1, nums2 = nums2, nums1  # Ensure nums1 is the smaller array

    low, high = 0, len(nums1)
    total_length = len(nums1) + len(nums2)

    while low <= high:
        partition_x = (low + high) // 2  # Find the partition point in nums1
        partition_y = (total_length + 1) // 2 - partition_x  # Find the partition point in nums2

        max_left_x = nums1[partition_x - 1] if partition_x > 0 else -sys.maxsize
        min_right_x = nums1[partition_x] if partition_x < len(nums1) else sys.maxsize

        max_left_y = nums2[partition_y - 1] if partition_y > 0 else -sys.maxsize
        min_right_y = nums2[partition_y] if partition_y < len(nums2) else sys.maxsize

        if max_left_x <= min_right_y and max_left_y <= min_right_x:
            # If the correct partition is found
            if total_length % 2 == 0:
                return (max(max_left_x, max_left_y) + min(min_right_x, min_right_y)) / 2
            else:
                return max(max_left_x, max_left_y)
        elif max_left_x > min_right_y:
            high = partition_x - 1
        else:
            low = partition_x + 1

    return 0