SDE - 1

/*
Approach 1: Brute Force TC: O(n) SC: O(n)
1. We Merge The Two Sorted Array (Basic Merging Method Of Merge Sort, With 2 Pointers.
2. We Find The Median Of The New Array.
*/
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {

int nums1Pointer = 0;
int nums2Pointer = 0;
int numsPointer = 0;
int[] nums = new int[nums1.length + nums2.length];

while(nums1Pointer < nums1.length && nums2Pointer < nums2.length){
if(nums1[nums1Pointer] < nums2[nums2Pointer]){
nums[numsPointer] = nums1[nums1Pointer];
nums1Pointer++;
}else{
nums[numsPointer] = nums2[nums2Pointer];
nums2Pointer++;
}
numsPointer++;
}

while(nums1Pointer nums2.length){
return findMedianSortedArrays(nums2, nums1);
}

// Applying Binary Search To The 2 Arrays
int nums1Length = nums1.length;
int nums2Length = nums2.length;
int start = 0;
int end = nums1Length;

while(start <= end){

int partition1 = start + (end-start)/2; // Mid Partition In The Smaller Size Array
int partition2 = (nums1Length + nums2Length + 1)/2 - partition1; // Mid Partition In The Larger Size Array

// Taking Left And Right Values Of The Partition Of Both The Arrays And Cross Checking Them
int left1 = (partition1 > 0)? nums1[partition1 - 1] : Integer.MIN_VALUE;
int left2 = (partition2 > 0)? nums2[partition2 - 1] : Integer.MIN_VALUE;

int right1 = (partition1 < nums1Length)? nums1[partition1] : Integer.MAX_VALUE;
int right2 = (partition2 < nums2Length)? nums2[partition2] : Integer.MAX_VALUE;

/*
If Left Value Of The First Array Is Smaller Than Right Value Of The Second Array 
And
Left Value Of The Second Array Is Smaller Than Right Value Of The First Array
Then
We Check If The Size Of The Sum Of Length Of Both Arrays Is Odd Or Even Because
If Odd, We Return The Max Of Left1 And Left2, And If Even We Return The Average
Of (Max(left1, left2) + Min(right1, right2)) / 2.0 as per the Average Formula.
*/
if(left1 <= right2 && left2 <= right1){
if((nums1Length + nums2Length) % 2 == 0){
return (Math.max(left1, left2) + Math.min(right1, right2)) / 2.0;
}
else{
return Math.max(left1, left2);
}
}
else if(left1 > right2){ // Base Binary Search Condition
end = partition1 - 1;
}
else{
start = partition1 + 1; // Base Binary Search Condition
}

}

// Default Return Input
return 0.0;

}
}

var multiply = function(num1, num2) {
return String(BigInt(num1) * BigInt(num2));
};

lass Solution {
public List restoreIpAddresses(String s) {
List ans = new ArrayList<>();

int len = s.length();
for(int i = 1; i < 4 && i < len-2 ; i++ ){
for(int j = i + 1; j < i + 4 && j < len-1 ; j++ ){
for(int k = j+1 ; k < j + 4 && k < len ; k++){
String s1 = s.substring(0,i);
String s2 = s.substring(i,j); 
String s3 = s.substring(j,k); 
String s4 = s.substring(k,len); 
if(isValid(s1) && isValid(s2) && isValid(s3) && isValid(s4))
ans.add(s1+"."+s2+"."+s3+"."+s4); 
}
}
}
return ans;
}
boolean isValid(String s){
if(s.length() > 3 || s.length()==0 || (s.charAt(0)=='0' && s.length()>1) || Integer.parseInt(s) > 255)
return false;
return true;
}
}

class Solution {
List> result = new ArrayList<>();
public List> combinationSum2(int[] candidates, int target) {
Arrays.sort(candidates);//sort the array thereby the logic for handling dupes will work properly
dfs(candidates,target,0,new ArrayList<>());
return result;
}
public void dfs(int[] candid,int target,int start,List sub){
//Base conditions
if(target < 0){
return;
}
if(target == 0){
result.add(new ArrayList<>(sub));
}
for(int i=start;i if(i != start && candid[i] == candid[i-1]){
continue;
}//logic to skip duplicates
sub.add(candid[i]);// add the present element to sub temporary list
dfs(candid,target-candid[i],i+1,sub);//call dfs recursively 
sub.remove(sub.size()-1);//backtrack the step by removing the last added data in the list which caused the problem to end so we backtrack by removing it from the list 
}
}
}