Author: devangini123

Problem Statement: Given a non-empty array of integers nums, every element appears twice except for one. Find that single one. You must implement a solution with a linear runtime complexity and use only constant extra space. Examples: Example 1: Input: nums = [2, 2, 1] Output: 1 Example 2: Input: nums = [4, 1, 2, 1, 2] Output: 4 Example 3: Input: nums = [1] Output: 1 Constraints: 1 ≤ nums.length ≤ 3 × 104 -3 × 104 ≤ nums[i] ≤ 3 × 104 Each element appears twice except one that appears only once. Approach 1 (Brute-force Hash Map): Create…

Problem Statement: Given an array nums containing n distinct numbers in the range [0, n], return the only number in the range that is missing from the array. Examples: Example 1: Input: nums = [3,0,1] Output: 2 Explanation: n = 3 since there are 3 numbers, so all numbers are in the range [0,3]. 2 is the missing number in the range since it does not appear in nums. Example 2: Input: nums = [0,1] Output: 2 Explanation: n = 2 since there are 2 numbers, so all numbers are in the range [0,2]. 2 is the missing number in…

🌙 Merge Sort Merge Sort is a popular divide-and-conquer sorting algorithm that divides the input array into two halves, recursively sorts them, and then merges the sorted halves into one sorted result. It is an example of a stable sort that guarantees O(n log n) performance in all cases — best, worst, and average. Approach: Divide: Split the array into two halves. Conquer: Recursively sort each half using merge sort. Combine: Merge the two sorted halves into one sorted array. Key Concept: Merge Step The key step is merging two sorted arrays efficiently into one sorted array. This is done…

🌙 Insertion Sort Insertion Sort is a simple and intuitive sorting algorithm that builds the final sorted array one element at a time. It works by taking each element from the input and inserting it into its correct position in the already sorted part of the array. Starting from the second element, it compares the current element with the previous ones, shifting larger elements one position ahead to make space for the current element. This process continues until all elements are sorted. Insertion Sort is efficient for small or nearly sorrted datasets and operates in-place without requiring extra memory. Approach:…

🌙 Selection Sort Selection Sort is a simple comparison-based sorting algorithm. It divides the array into two parts: a sorted subarray and an unsorted subarray. Initially, the sorted part is empty, and the unsorted part is the entire array. In each iteration, it finds the minimum element from the unsorted part and moves it to the end of the sorted part. Example 1: Input: [4, 5, 1, 3, 9] Output: [1, 3, 4, 5, 9] Approach: Iterate over the array from index 0 to n-2. For each index i, assume the element at i is the minimum in the unsorted…

🌙 Bubble Sort Bubble Sort is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. This process is repeated until the array is sorted. After each pass, the largest unsorted element “bubbles up” to its correct position at the end of the array. It’s called “Bubble Sort” As smaller elements slowly “bubble” to the top of the list. Approach: Iterate through the array multiple times. In each pass, compare adjacent elements. If the current element is greater than the next one, swap them. After each pass,…

🌙 Binary Search Binary Search is an efficient algorithm used to find the position of a target value within a sorted array. Unlike linear search, it repeatedly divides the search interval in half, significantly reducing the number of comparisons. Example 1: Input: [1, 3, 5, 7, 9] Output: 7 Approach: Set left = 0 right = nums.length – 1. While left nums[middle] → left = middle + 1 = 3 State: left = 3, right = 5 Iteration 2: middle = Math.floor((3 + 5) / 2) = 4 nums[4] = 9 target = 9 → target === nums[middle] → return…

🌙 Linear Search Linear Search is a simple search algorithm used to find a specific element in an array. It checks each element of the array one by one until the target value is found or the end of the array is reached. Example 1: Input: arr = [2, 4, 7, 10], target = 10 Output: 3 Explanation: 10 is found at index 3 Example 2: Input: arr = [6, 8, 0, 3], target = 5 Output: -1 Explanation: 5 is not present in the array Approach: Start from the first element of the array. Compare the current element with…

🌙 What is a Fibonacci Number? The Fibonacci sequence is a famous mathematical series in which each number is the sum of two preceding ones It’s defined by the recurrence relation: F(0) = 0 F(1) = 1 F(n) = F(n-1) + F(n-2) for n > 1 This generates a series like: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, … Each number is the sum of the two before it. This sequence appears frequently in nature (e.g., flower petals, pine cones, and spiral shells), in algorithms (like dynamic programming), and even in computer science problems related to recursion,…

🌙 Problem Statement: Write a recursive function isPowerOfTwo(n) that returns true if n is a power of 2, otherwise false. Example 1: Input: 8 Process: (8 → 4 → 2 → 1) Output: true Example 2: Input: 18 Output: false Concepts: Power of Two: A number is a power of 2 if it can be divided by 2 repeatedly until it reaches 1. Base Case: n == 1 → true Invalid Case: n < 1 or n % 2 != 0 → false Recursive Case: isPowerOfTwo(n / 2) Time & Space Complexity: Time Complexity: O(log n) Space Complexity: O(log n)…