Arrays

Medium

1. Re-arrange the elements alternating sign

   • This can’t be done in-place, if done its O(n^2)
   • Make a new array & two pointers, to track pos & neg, and do pointers +2

2. Print matrix in spiral NxM

   • Four pointers, top=0, bottom=n-1, left=0, right=m-1
   • Loop of top <= bottom && left <= right
   • Imp. to check top <= bottom before going right to left, because top++ has been done.
   • Imp. to check left <= right before going bottom to top as bottom++ has been done.

3. Pascal’s triangle

   • starts with 1,
   • below row is ∑ (above two)
   • each row have addition of 1 extra
   • arrange in triangle but might not be seen in a question

   3.1 The value of number at r^th row and c^th column can be calculated as binomial coefficient Formula = nCr = nC(n-r) = n!/(n-r)!r! Choose r or (n-r) whichever is smaller.

   Formula Algorithm for nCr:

   if( r > n-r )
   	r = n-r;
    
   if( r == 1 )
   	return n;
    
   res = 1;
    
   for( int i = 0; i<r; i++ ) {
   	res = res * (n-i);
   	res = res / (i+1);
   }
    
   return res;

4. Pascal’s Triangle - I Find element at r row and c column → Use the nCr formula

5. Pascal’s Triangle - II Find the elements in the rth row. Algorithm:

    
   // Iterate from i = 1 to r;
   // current = prev * (r-i) / i;
    
   let res = [];
   res[0] = 1;
   for(let i=1; i<r; i++) {
   	res[i] = (res[i-1] * (r-j))/j;
   }
    
   return res;

6. Pascal’s Triangle - III Generate the whole triangle

   • Use function to generate row by using res[i] = (res[i-1]*(r-i))/j
   • Loop this function for 1 to <=n

7. Rotate matrix by 90degree Transpose & Reverse

   • Better to reverse first
   • In transpose make sure to run (j<i)

8. 3 Sum

   • Imp. that using hashMap looks tempting, but its not efficient. If duplicates are not allowed, then extra sorting will required. Using hashMap, space complexity is O(n), and no save in timecomplexity.
   • Don’t fix two numbers and binary search the third one, it will be O(n^2 log(n))

   Algorithm:

   • Sort the array
   • Fix a pointer, and then move 2 pointers from start and end based on sum.

   let que = [-1, 0, 1, 2, -1, -4];
    
   let arr = que.sorted();
    
   let res = [];
    
   for(let i = 0; i<(n-2); i++) (
   	if(i> 0 && arr[i] == arr[i-1]) continue; // Skip the duplicates
    
   	let j=i+1, k=n-1;
   	while(j<k) {
   		let sum = arr[i] + arr[j] + arr[k];
   		if( sum === 0 ) { 
   			res.push([arr[i],arr[j],arr[k]]);
   			k--;
   			j++;
   		} else if( sum > 0 )
   			k--;
   		else
   			j++;
   	}
   )

9. 4-Sum problem This is done similar to 3-sum problem. Added with last two elements are found using another loop and target.

   for(let i=0; i<(n-3); i++) {
   	if( i>0 && nums[i] == nums[i-1] ) continue;
    
   	for(let j=i+1; j<(n-2); j++) {
   		if( j>0 && nums[j] == nums[j-1] ) continue;
   		
   		let left = j+1;
   		let right = n-1;
   		
   		const target2 = target - (nums[i] + nums[j]);
   		
   		while( left < right ) {
   			const sum = nums[left] + nums[right];
   			
   			if(sum === target2) {
   				res.push( /** All four nums */ );
   				left++;
   				right--;
   			} else if(sum > target2) {
   				right--;
   			} else {
   				left++;
   			}
   		}	
   	}
   }

10. Majority Elements Find the number which occurs more than, n/2 times.

    • Brute force is to create a Map, count each number occurrence and then iterate map to find which one is more than n/2 times.
    • Optimized approach or trick is, create variables Candidate = nums[0],Count. Iterate on the array.

    The algorithm finds the majority element by using vote counting:

    • Pick a candidate.
      When count becomes 0, choose the current number as the new candidate.
    • Increase count if the current number equals the candidate.
    • Decrease count if it’s different (cancel one vote). Because the majority element appears more than half,
      it cannot be cancelled completely, and it will remain as the final candidate

    let candidate=0;
    let count=0;
     
    for(let i=0; i<nums.length; i++) {
    	let num = nums[i];
    	
    	if( count == 0 ) {
    	// This means, till now no number is repeated, so current number can be the candidate
    		count = 1;
    		candidate = num; // Selecting a number as candidate
    	} else if( candidate == num ) count++;
    	else count--;
    }
     
    return candidate;

11. Kadane’s Algo Keep running in sub-array sum until you find a negative sum, track the maximum sum so far.

    let maxSum = -Infinity;
    let currentSum = 0;
     
    for(let num of nums) {
    	currentSum += num;
    	maxSum = Math.max(currentSum, maxSum);
    	if( currentSum < 0 ) currentSum = 0;
    }
     
    return maxSum;

Hard

1. Majority Element II for n/3 Here the Boyer-moore algo can be generalized.
   • Boyer–Moore cancels groups of k distinct elements for n/k majority. So you maintain k–1 candidates, because only k–1 numbers can appear more than n/k times.

   class Solution {
   majorityElementTwo(nums) {
       let cand1 = null, cand2 = null;
       let count1 = 0, count2 = 0;
    
       // 1. Boyer–Moore candidate selection
       for (let num of nums) {
           if (num === cand1) {
               count1++;
           } else if (num === cand2) {
               count2++;
           } else if (count1 === 0) {
               cand1 = num;
               count1 = 1;
           } else if (count2 === 0) {
               cand2 = num;
               count2 = 1;
           } else {
               count1--;
               count2--;
           }
       }
    
       // 2. Verify the candidates
       count1 = 0;
       count2 = 0;
    
       for (let num of nums) {
           if (num === cand1) count1++;
           else if (num === cand2) count2++;
       }
    
       const threshold = Math.floor(nums.length / 3);
       const result = [];
    
       if (count1 > threshold) result.push(cand1);
       if (count2 > threshold) result.push(cand2);
    
       return result;
   }
   }
   	```
    

2. Find the missing and the repeating number Need to remember the math equation.

   Repeating = R = (X + Y/X) / 2
   Missing = M = R - X;
   
   Where:
   X = S - Sn;
   Y = S2 - S2n;