Leet Code Problems

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