# Top 100 Problems on LeetCode and its Solutions – Part1

## 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:

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

- 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:

- Initialize a dummy node and a carry variable.
- Iterate through the input lists until we reach the end of both lists.
- Add the values of the nodes, if they exist, and the carry.
- Calculate the new carry and the value of the current node.
- Move to the next nodes and repeat steps 2-4.
- If there’s a carry left at the end, add a new node with the carry value.
- 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:

- Initialize a hashmap to store the index of characters.
- Initialize two pointers, left and right, to iterate through the string.
- Iterate through the string with the right pointer.
- 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.
- Update the hashmap with the new character index.
- 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:

- Ensure that nums1 is the smaller array. If not, swap nums1 and nums2.
- Find the partition points in both arrays such that the left half has the same number of elements as the right half.
- Binary search on the smaller array to find the correct partition points.
- 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
```