CodeWithClarity

 You are climbing a staircase. It takes n steps to reach the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top? Example 1: Input: n = 2 Output: 2 Explanation: There are two ways to climb to the top. 1. 1 step + 1 step 2. 2 steps Example 2: Input: n = 3 Output: 3 Explanation: There are three ways to climb to the top. 1. 1 step + 1 step + 1 step 2. 1 step + 2 steps 3. 2 steps + 1 step Approach 1 Basic Recursion -Problem TLE class Solution {     public int climbStairs ( int n ) {               if (n== 0 ) return 1 ;       if (n< 0 ) return 0 ;       return climbStairs (n- 1 )+ climbStairs (n- 2 );     } } It recalculates the same subproblems many times . Time complexity: O(2ⁿ) → This will timeout for large n (like n = 45 or more). Approach 2- Add Memoization (Top-Down + Cache) class Solution {     public int climbStai...

 Given an array of integers arr, replace each element with its rank. The rank represents how large the element is. The rank has the following rules: Rank is an integer starting from 1. The larger the element, the larger the rank. If two elements are equal, their rank must be the same. Rank should be as small as possible.   Example 1: Input: arr = [40,10,20,30] Output: [4,1,2,3] Explanation: 40 is the largest element. 10 is the smallest. 20 is the second smallest. 30 is the third smallest. Example 2: Input: arr = [100,100,100] Output: [1,1,1] Explanation: Same elements share the same rank. Example 3: Input: arr = [37,12,28,9,100,56,80,5,12] Output: [5,3,4,2,8,6,7,1,3]   class Solution {     public int [] arrayRankTransform ( int [] arr ) {         // Step 1: Use TreeSet to store unique elements in sorted order         Set < Integer > set = new TreeSet <>();         // Add all elements t...

 You are part of a university admissions office and need to keep track of the kth highest test score from applicants in real-time. This helps to determine cut-off marks for interviews and admissions dynamically as new applicants submit their scores. You are tasked to implement a class which, for a given integer k, maintains a stream of test scores and continuously returns the kth highest test score after a new score has been submitted. More specifically, we are looking for the kth highest score in the sorted list of all scores. Implement the KthLargest class: KthLargest(int k, int[] nums) Initializes the object with the integer k and the stream of test scores nums. int add(int val) Adds a new test score val to the stream and returns the element representing the kth largest element in the pool of test scores so far.   Example 1: Input: ["KthLargest", "add", "add", "add", "add", "add"] [[3, [4, 5, 8, 2]], [3], [5], [10], [9], [4...

 Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.   Example 1: Input: nums = [1,1,1,2,2,3], k = 2 Output: [1,2] Example 2: Input: nums = [1], k = 1 Output: [1] class Solution {     public int [] topKFrequent ( int [] nums , int k ) {                 HashMap < Integer , Integer > map = new HashMap <>();         for ( int num : nums)         {             map . put (num, map . getOrDefault (num, 0 )+ 1 );         }         PriorityQueue < Map . Entry < Integer , Integer >> heap = new PriorityQueue <>((a,b) -> a . getValue ()- b . getValue ());         for ( Map . Entry < Integer , Integer > entry : map . entrySet ())         {           ...

 You are given two integer arrays nums1 and nums2 sorted in non-decreasing order and an integer k. Define a pair (u, v) which consists of one element from the first array and one element from the second array. Return the k pairs (u1, v1), (u2, v2), ..., (uk, vk) with the smallest sums.   Example 1: Input: nums1 = [1,7,11], nums2 = [2,4,6], k = 3 Output: [[1,2],[1,4],[1,6]] Explanation: The first 3 pairs are returned from the sequence: [1,2],[1,4],[1,6],[7,2],[7,4],[11,2],[7,6],[11,4],[11,6] Example 2: Input: nums1 = [1,1,2], nums2 = [1,2,3], k = 2 Output: [[1,1],[1,1]] Explanation: The first 2 pairs are returned from the sequence: [1,1],[1,1],[1,2],[2,1],[1,2],[2,2],[1,3],[1,3],[2,3]  Brurte Force : import java.util.*; class Solution {     public List < List < Integer >> kSmallestPairs ( int [] nums1 , int [] nums2 , int k ) {         PriorityQueue < int []> maxHeap = new PriorityQueue <>(       ...

 You are given an array of integers stones where stones[i] is the weight of the ith stone. We are playing a game with the stones. On each turn, we choose the heaviest two stones and smash them together. Suppose the heaviest two stones have weights x and y with x <= y. The result of this smash is: If x == y, both stones are destroyed, and If x != y, the stone of weight x is destroyed, and the stone of weight y has new weight y - x. At the end of the game, there is at most one stone left. Return the weight of the last remaining stone. If there are no stones left, return 0.   Example 1: Input: stones = [2,7,4,1,8,1] Output: 1 Explanation:  We combine 7 and 8 to get 1 so the array converts to [2,4,1,1,1] then, we combine 2 and 4 to get 2 so the array converts to [2,1,1,1] then, we combine 2 and 1 to get 1 so the array converts to [1,1,1] then, we combine 1 and 1 to get 0 so the array converts to [1] then that's the value of the last stone. Example 2: Input: stones = [1] Ou...

 Given are N ropes of different lengths, the task is to connect these ropes into one rope with minimum cost, such that the cost to connect two ropes is equal to the sum of their lengths. Input: arr[] = {4,3,2,6} , N = 4 Output: 29 Explanation: First, connect ropes of lengths 2 and 3. Now we have three ropes of lengths 4, 6, and 5. Now connect ropes of lengths 4 and 5. Now we have two ropes of lengths 6 and 9. Finally connect the two ropes and all ropes have connected. Input: arr[] = {1, 2, 3} , N = 3 Output: 9 Constraints: N == arr.length 0 <= N <= 10^4 1 <= arr[i].length <= 10^4 🔄 Step-by-step Dry Run: Initial ropes: [4, 3, 2, 6] Pick 2 smallest ropes → 2 + 3 = 5 → cost = 5 → add back → [4, 5, 6] Pick 2 smallest → 4 + 5 = 9 → cost = 9 → add back → [6, 9] Pick 2 smallest → 6 + 9 = 15 → cost = 15 → final rope 🧮 Total Cost = 5 + 9 + 15 = 29  Why Use Min-Heap (PriorityQueue)? To always get the smallest 2 ropes in O(log N) time. import java . util ....

 iven the head of a linked list and an integer val, remove all the nodes of the linked list that has Node.val == val, and return the new head.   Example 1: Input: head = [1,2,6,3,4,5,6], val = 6 Output: [1,2,3,4,5] Example 2: Input: head = [], val = 1 Output: [] Example 3: Input: head = [7,7,7,7], val = 7 Output: []   Constraints: The number of nodes in the list is in the range [0, 10^4]. We'll use a dummy node to handle edge cases like removing the head. Steps: Create a dummy node ( dummy ) before the head. Use a current pointer starting from dummy . Loop while current.next is not null: If current.next.val == val , skip it using current.next = current.next.next Else, move forward. Return dummy.next (new head). class ListNode {     int val ;     ListNode next ;     ListNode ( int val ) {         this . val = val;     } } public class Solution {     public ListNode rem...

 Given the head of a linked list, remove the nth node from the end of the list and return its head.   Example 1: Input: head = [1,2,3,4,5], n = 2 Output: [1,2,3,5] Example 2: Input: head = [1], n = 1 Output: [] Example 3: Input: head = [1,2], n = 1 Output: [1]   Constraints: The number of nodes in the list is sz. 1 <= sz <= 30 0 <= Node.val <= 100 1 <= n <= sz   Follow up: Could you do this in one pass? 🔷 Step-by-Step Logic: First traverse the list once to count total nodes . Then calculate the position to delete from the start: pos = total - n Traverse again up to that pos . Use two pointers: prev and current . When pos == 0 , skip the node by: prev.next = current.next; /**  * Definition for singly-linked list.  * public class ListNode {  *     int val;  *     ListNode next;  *     ListNode() {}  *     ListNode(int val) { this.val = val; }  *   ...

 Given head, the head of a linked list, determine if the linked list has a cycle in it. There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail's next pointer is connected to. Note that pos is not passed as a parameter. Return true if there is a cycle in the linked list. Otherwise, return false.   Example 1: Input: head = [3,2,0,-4], pos = 1 Output: true Explanation: There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed). Example 2: Input: head = [1,2], pos = 0 Output: true Explanation: There is a cycle in the linked list, where the tail connects to the 0th node. Example 3: Input: head = [1], pos = -1 Output: false Explanation: There is no cycle in the linked list.   Constraints: The number of the nodes in the list is in the range [0, 104]. -105 <= Node.val <= 10^5 pos is -1 or a valid i...