CodeWithClarity

 Given a string s, you can transform every letter individually to be lowercase or uppercase to create another string. Return a list of all possible strings we could create. Return the output in any order.   Example 1: Input: s = "a1b2" Output: ["a1b2","a1B2","A1b2","A1B2"] Example 2: Input: s = "3z4" Output: ["3z4","3Z4"] class Solution {     public List < String > letterCasePermutation ( String s ) {                 List < String > result = new ArrayList <>();         StringBuilder builder = new StringBuilder ();         int start = 0 ;         backtrack (s,start,builder,result);         return result;     }     public static void backtrack ( String s , int start , StringBuilder builder , List < String > result )     {         //base case       ...

 Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s.   Example 1: Input: s = "aab" Output: [["a","a","b"],["aa","b"]] Example 2: Input: s = "a" Output: [["a"]] class Solution {     public List < List < String >> partition ( String s ) {           List < List < String >> result = new ArrayList <>();         backtrack (s, 0 , new ArrayList <>(), result);         return result;     }       private void backtrack ( String s , int startIndex , List < String > currentPartition , List < List < String >> allPartitions ) {         if (startIndex == s . length ()) {             allPartitions . add ( new ArrayList <>(currentPartition));             ret...

 Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sum to target. Each number in candidates may only be used once in the combination. Note: The solution set must not contain duplicate combinations.   Example 1: Input: candidates = [10,1,2,7,6,1,5], target = 8 Output:  [ [1,1,6], [1,2,5], [1,7], [2,6] ] Example 2: Input: candidates = [2,5,2,1,2], target = 5 Output:  [ [1,2,2], [5] ] class Solution {     public List < List < Integer >> combinationSum2 ( int [] candidates , int target ) {         List < List < Integer >> result = new ArrayList <>();         Arrays . sort (candidates);         backtrack (candidates, 0 , target, new ArrayList <>(), result);         return result;     }       private void backtra...

 Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. You may return the combinations in any order. The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if the frequency of at least one of the chosen numbers is different. The test cases are generated such that the number of unique combinations that sum up to target is less than 150 combinations for the given input.   Example 1: Input: candidates = [2,3,6,7], target = 7 Output: [[2,2,3],[7]] Explanation: 2 and 3 are candidates, and 2 + 2 + 3 = 7. Note that 2 can be used multiple times. 7 is a candidate, and 7 = 7. These are the only two combinations. Example 2: Input: candidates = [2,3,5], target = 8 Output: [[2,2,2,2],[2,3,3],[3,5]] Example 3: Input: candidates = [2], target = 1 Output: [] 1. Approach (Idea) Use Backtracking to explore all combinations. ...

 Given an integer array nums of unique elements, return all possible subsets (the power set). The solution set must not contain duplicate subsets. Return the solution in any order. Example 1: Input: nums = [1,2,3] Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]] Example 2: Input: nums = [0] Output: [[],[0]] import java.util.*; public class Solution {     public List < List < Integer >> subsets ( int [] nums ) {         List < List < Integer >> result = new ArrayList <>();         List < Integer > temp = new ArrayList <>();         backtrack (nums, 0 , temp, result);         return result;     }     private void backtrack ( int [] nums , int start , List < Integer > temp , List < List < Integer >> result ) {                 result . add ( new ArrayList <>...

 Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.   Example 1: Input: nums = [1,2,3] Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]] Example 2: Input: nums = [0,1] Output: [[0,1],[1,0]] Example 3: Input: nums = [1] Output: [[1]] import java.util.*; class Solution {     public List < List < Integer >> permute ( int [] nums ) {         List < List < Integer >> result = new ArrayList <>(); // to store all permutations         boolean [] used = new boolean [ nums . length ]; // track used elements         List < Integer > path = new ArrayList <>(); // current permutation path         backtrack (nums, path, used, result);         return result;     }     private void backtrack ( int [] nums , List < Integer > path ...

 Implement pow(x, n), which calculates x raised to the power n (i.e., xn).   Example 1: Input: x = 2.00000, n = 10 Output: 1024.00000 Example 2: Input: x = 2.10000, n = 3 Output: 9.26100 Example 3: Input: x = 2.00000, n = -2 Output: 0.25000 Explanation: 2-2 = 1/22 = 1/4 = 0.25 class Solution {     public double pow ( double x , long n ) {         if (n == 0 ) return 1.0 ;   //  important base case         if (x == 0 ) return 0.0 ;   //  handle x=0 separately (optional)         double half = pow (x, n/ 2 );   //2*n/2=n         if (n % 2 == 0 ) {             return half * half;         } else {             return x * half * half;         }     }     public double myPow ( double x , int n ) {         long N ...

Given a non-negative integer x, return the square root of x rounded down to the nearest integer. The returned integer should be non-negative as well. You must not use any built-in exponent function or operator. For example, do not use pow(x, 0.5) in c++ or x ** 0.5 in python.   Example 1: Input: x = 4 Output: 2 Explanation: The square root of 4 is 2, so we return 2. Example 2: Input: x = 8 Output: 2 Explanation: The square root of 8 is 2.82842..., and since we round it down to the nearest integer, 2 is returned. class Solution {     public int mySqrt ( int x ) {         // Base cases: if x is 0 or 1, square root is the number itself         if (x == 0 || x == 1 ) return x;                 int start = 1 ;       // Minimum possible square root         int end = x;         // Maximum possible square root       ...

Koko loves to eat bananas. There are n piles of bananas, the ith pile has piles[i] bananas. The guards have gone and will come back in h hours. Koko can decide her bananas-per-hour eating speed of k. Each hour, she chooses some pile of bananas and eats k bananas from that pile. If the pile has less than k bananas, she eats all of them instead and will not eat any more bananas during this hour. Koko likes to eat slowly but still wants to finish eating all the bananas before the guards return. Return the minimum integer k such that she can eat all the bananas within h hours.   Example 1: Input: piles = [3,6,7,11], h = 8 Output: 4 Example 2: Input: piles = [30,11,23,4,20], h = 5 Output: 30 Example 3: Input: piles = [30,11,23,4,20], h = 6 Output: 23 class Solution {     // Helper function to find maximum pile value     public static int maxsum ( int [] arr ) {         int sum = 0 ;         for ( int a : arr) { ...

 In the universe Earth C-137, Rick discovered a special form of magnetic force between two balls if they are put in his new invented basket. Rick has n empty baskets, the ith basket is at position[i], Morty has m balls and needs to distribute the balls into the baskets such that the minimum magnetic force between any two balls is maximum. Rick stated that magnetic force between two different balls at positions x and y is |x - y|. Given the integer array position and the integer m. Return the required force.   Example 1: Input: position = [1,2,3,4,7], m = 3 Output: 3 Explanation: Distributing the 3 balls into baskets 1, 4 and 7 will make the magnetic force between ball pairs [3, 3, 6]. The minimum magnetic force is 3. We cannot achieve a larger minimum magnetic force than 3. Example 2: Input: position = [5,4,3,2,1,1000000000], m = 2 Output: 999999999 Explanation: We can use baskets 1 and 1000000000.   class Solution {     public int maxDistance ( int [] posit...

 You are given an array with unique elements of stalls[], which denote the position of a stall. You are also given an integer k which denotes the number of aggressive cows. Your task is to assign stalls to k cows such that the minimum distance between any two of them is the maximum possible. Examples : Input: stalls[] = [1, 2, 4, 8, 9], k = 3 Output: 3 Explanation: The first cow can be placed at stalls[0],  the second cow can be placed at stalls[2] and  the third cow can be placed at stalls[3].  The minimum distance between cows, in this case, is 3, which also is the largest among all possible ways. Input: stalls[] = [10, 1, 2, 7, 5], k = 3 Output: 4 Explanation: The first cow can be placed at stalls[0], the second cow can be placed at stalls[1] and the third cow can be placed at stalls[4]. The minimum distance between cows, in this case, is 4, which also is the largest among all possible ways. Input: stalls[] = [2, 12, 11, 3, 26, 7], k = 5 Output: 1 Explanation: Eac...

 A conveyor belt has packages that must be shipped from one port to another within days days. The ith package on the conveyor belt has a weight of weights[i]. Each day, we load the ship with packages on the conveyor belt (in the order given by weights). We may not load more weight than the maximum weight capacity of the ship. Return the least weight capacity of the ship that will result in all the packages on the conveyor belt being shipped within days days.   Example 1: Input: weights = [1,2,3,4,5,6,7,8,9,10], days = 5 Output: 15 Explanation: A ship capacity of 15 is the minimum to ship all the packages in 5 days like this: 1st day: 1, 2, 3, 4, 5 2nd day: 6, 7 3rd day: 8 4th day: 9 5th day: 10 Note that the cargo must be shipped in the order given, so using a ship of capacity 14 and splitting the packages into parts like (2, 3, 4, 5), (1, 6, 7), (8), (9), (10) is not allowed. Example 2: Input: weights = [3,2,2,4,1,4], days = 3 Output: 6 Explanation: A ship capacity of 6 is th...

 You are given an array arr[] of integers, where each element arr[i] represents the number of pages in the ith book. You also have an integer k representing the number of students. The task is to allocate books to each student such that: Each student receives atleast one book. Each student is assigned a contiguous sequence of books. No book is assigned to more than one student. The objective is to minimize the maximum number of pages assigned to any student. In other words, out of all possible allocations, find the arrangement where the student who receives the most pages still has the smallest possible maximum. Note: Return -1 if a valid assignment is not possible, and allotment should be in contiguous order (see the explanation for better understanding). Examples: Input: arr[] = [12, 34, 67, 90], k = 2 Output: 113 Explanation: Allocation can be done in following ways: [12] and [34, 67, 90] Maximum Pages = 191 [12, 34] and [67, 90] Maximum Pages = 157 [12, 34, 67] and [90] Maximum...

 You are given an integer n. Each number from 1 to n is grouped according to the sum of its digits. Return the number of groups that have the largest size.   Example 1: Input: n = 13 Output: 4 Explanation: There are 9 groups in total, they are grouped according sum of its digits of numbers from 1 to 13: [1,10], [2,11], [3,12], [4,13], [5], [6], [7], [8], [9]. There are 4 groups with largest size. Example 2: Input: n = 2 Output: 2 Explanation: There are 2 groups [1], [2] of size 1. class Solution {     public int countLargestGroup ( int n ) {     // Step 1: Create an array to store the count of each digit sum     int [] count = new int [ 37 ]; // Max digit sum is 9+9+9 = 27 (safe to use 37)     // Step 2: Loop from 1 to n     for ( int i = 1 ; i <= n; i++) {         int sum = digitSum (i);     // calculate digit sum         count[sum]++;        ...

 Given an integer n, return the nth digit of the infinite integer sequence [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ...].   Example 1: Input: n = 3 Output: 3 Example 2: Input: n = 11 Output: 0 Explanation: The 11th digit of the sequence 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ... is a 0, which is part of the number 10. class Solution {     public int findNthDigit ( int n ) {         int digitLength = 1 ; // Numbers start as 1-digit         long count = 9 ;       // 9 one-digit numbers         long start = 1 ;       // Starting number in this range         // Step 1: Find which digit-length group contains the nth digit         while (n > digitLength * count) {             n -= digitLength * count; // Remove the full range of digits             digitLength++;     ...

 The Hamming distance between two integers is the number of positions at which the corresponding bits are different. Given an integer array nums, return the sum of Hamming distances between all the pairs of the integers in nums. Example 1: Input: nums = [4,14,2] Output: 6 Explanation: In binary representation, the 4 is 0100, 14 is 1110, and 2 is 0010 (just showing the four bits relevant in this case). The answer will be: HammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14, 2) = 2 + 2 + 2 = 6. Example 2: Input: nums = [4,14,4] Output: 4   Approach 1 : -Brute Force (issue in brute force is Time Limit Exceeded problem class Solution {     public int totalHammingDistance ( int [] nums ) {         int distnace = 0 ;         for ( int i = 0 ;i< nums . length ;i++)         {             for ( int j =i+ 1 ;j< nums . length ;j++)       ...