Leet Code Problems

Optimizing MySQL Queries for Finding Top Earners by Department Optimizing MySQL Queries for Finding Top Earners by Department In this blog post, we’ll explore how to write and optimize a MySQL query to find employees with the highest salary in each department. This is a common problem in database querying, often encountered in interviews and real-world applications. We’ll compare two solutions: one using a correlated subquery and an optimized version using a Common Table Expression (CTE). We’ll explain the approach, logic, time complexity, and provide the complete SQL code for both. Problem Statement Given two tables: Employee : Contains employee details with columns id , name , salary , and departmentId . Department : Contains department details with columns id and name . We need to find each employee who earns the highest salary in their department, returning the department name, employee name, and salary....

🔍 Finding the Closest Prime Numbers in a Range using the Sieve of Eratosthenes Prime numbers play a crucial role in number theory and various computational applications. In this blog, we will explore an optimized approach to finding the two closest prime numbers within a given range using the Sieve of Eratosthenes . 🚀 📌 Problem Statement Given two integers left and right , find the two prime numbers within the range [left, right] that have the smallest difference. If there are fewer than two prime numbers, return [-1, -1] . 🛠️ Approach To efficiently solve this problem, we use the Sieve of Eratosthenes algorithm to precompute prime numbers up to right . Then, we extract the prime numbers from the given range and find the closest pair. ✅ Steps to Solve Initialize a boolean list primes where primes[i] = True indicates i is prime. Mark 0 and 1 as Fa...

Optimized Count of Good Numbers | O(log n) Solution Optimized Count of Good Numbers | O(log n) Solution 🚀 Introduction Counting "Good Numbers" is an interesting problem that requires us to efficiently compute large exponentiations while following specific digit placement rules. This blog post explores an optimized approach using modular exponentiation , breaks down the logic, and provides a dry run for better understanding. Problem Statement Given an integer n , we need to find how many valid numbers of length n can be formed such that: Digits at even indices (0-based) must be even (0, 2, 4, 6, 8) → 5 choices Digits at odd indices must be prime (2, 3, 5, 7) → 4 choices Since the result can be large, we return it modulo 10⁹ + 7 . Optimized Approach To construct such numbers, we can observe: Even-indexed positions contribute 5^(odd_count) Odd-indexed po...

Understanding the Fast Exponentiation Algorithm: Exponentiation by Squaring In this blog post, we will explore the implementation of the myPow function, a common problem found on LeetCode. The goal of this problem is to compute \(x^n\) efficiently, even when \(n\) is a very large number. Instead of using a naive approach, we employ a method called Exponentiation by Squaring to significantly reduce the number of multiplications required. Problem Overview Given a floating-point number x and an integer n , our task is to implement a function that computes \(x^n\). A straightforward solution might involve multiplying x by itself n times, but this approach is too slow when n is large. Intuition Behind Exponentiation by Squaring The main idea is to reduce the problem size by halving the exponent at each recursive step. Consider the following: If n is even, then: \(x^n = x^{...

Three Sum Closest - LeetCode Solution In this blog post, we'll dive into the Three Sum Closest problem, a popular coding challenge on LeetCode. We'll explore the intuition behind the solution, discuss the approach, analyze the complexity, and provide a detailed explanation of the code. Additionally, I'll share my LeetCode solution link for further reference. Problem Statement Given an integer array nums of length n and an integer target , find three integers in nums such that the sum is closest to target . Return the sum of the three integers. You may assume that each input would have exactly one solution. Intuition The problem requires finding three numbers in the array whose sum is as close as possible to the target. To efficiently find such a triplet, we can use a combination of sorting and the two-pointer technique . Sorting : First, sort the array. This allows us to use the two-po...

String to Integer (atoi) – A Step-by-Step Guide Introduction Converting a string to an integer is a common problem in programming. In this blog, we will walk through a simple approach to implementing the atoi function. Approach Trim leading whitespace from the string. Check if the first character is a sign (`+` or `-`) and store it. Extract numeric characters and form the number. Convert the numeric string to an integer and apply the sign. Clamp the result within the 32-bit integer range (`[-2147483648, 2147483647]`). Code Implementation class Solution: def myAtoi(self, s: str) -> int: s = s.strip() sign = 1 result = "0" for i, c in enumerate(s): if i == 0: if c == '-': sign = -1 elif c == '+...

Rearrange Array Elements by Sign Introduction In this blog, we will discuss two approaches to solving the problem of rearranging an array such that positive and negative numbers appear alternately while maintaining their relative order. Method 1: Using Separate Lists This approach involves separating positive and negative numbers into two different lists and then merging them back into the original array. Steps: Create two lists: one for positive numbers and one for negative numbers. Iterate through the given array and store positive numbers in one list and negative numbers in another. Reconstruct the array by alternating elements from both lists. Code: class Solution: def rearrangeArray(self, nums: List[int]) -> List[int]: positive = [] negative = [] for i in nums: if i Time Complexity: O(n) - We traverse the array twice, once to separa...

Maximum Subarray Problem - LeetCode Solution Maximum Subarray Problem - LeetCode Solution Problem Statement Given an integer array nums , find the contiguous subarray (containing at least one number) that has the largest sum and return its sum. Intuition The problem requires finding the contiguous subarray with the maximum sum. A brute force approach would involve checking all subarrays, but this would be inefficient. Instead, we use Kadane's Algorithm , which efficiently finds the maximum sum subarray in O(n) time. Approach Initialize two variables: total (running sum) and maxi (maximum sum encountered so far). Iterate through the array: Add the current element to total . Update maxi with the maximum of maxi and total . If total becomes negative, reset it to zero. Return maxi as the maximum sub...

Sorting Colors in Python: A Step-by-Step Guide Sorting Colors in Python: A Step-by-Step Guide In this blog post, we'll dive into a common problem known as the "Dutch National Flag problem." The goal is to sort an array containing three distinct integers representing colors. Specifically, we'll sort an array of colors where 0, 1, and 2 represent red, white, and blue, respectively. We'll use a simple counting approach to achieve this. Problem Statement 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. The Solution We'll use a dictionary to count the occurrences of each color and then overwrite the original array based on these counts. Step-by-Step Explanation Step 1: Initialize a Dictionary with Counts We start by initializing a dictionary using dict.fromkeys...

  Finding the First and Last Position of an Element in a Sorted Array Using Binary Search Introduction Searching for an element in a sorted array is a common problem in computer science, and one of the most efficient ways to solve it is by using Binary Search . In this blog post, we'll discuss how to find the first and last positions of a target element in a sorted array using an optimized binary search approach. We'll also analyze its time complexity and why it outperforms brute-force methods. Problem Statement Given an array of integers nums sorted in non-decreasing order, we need to find the starting and ending position of a given target value. If target is not found, we return [-1, -1] . The solution must have a time complexity of O(log n) . Approach: Modified Binary Search Since the array is sorted, binary search is an ideal approach. Instead of a single search, we perform two separate searches: Finding the Leftmost Index : We modify the binary search to cont...