Algorithm-Java-programming- Arrays

add-one-to-number

https://www.interviewbit.com/problems/add-one-to-number/

						import java.util.ArrayList;
			import java.util.Arrays;

			public class AddOneToNumber {

				public static void main(String[] args) {
					System.out.println(Arrays.toString(addOne(new int[] {})));
					System.out.println(Arrays.toString(addOne(new int[] { 1 })));
					System.out.println(Arrays.toString(addOne(new int[] { 9 })));
					System.out.println(Arrays.toString(addOne(new int[] { 3, 9, 9 })));
					System.out.println(Arrays.toString(addOne(new int[] { 3, 9, 9, 9 })));
					System.out.println(Arrays.toString(addOne(new int[] { 9, 9, 9, 9 })));
					System.out.println(Arrays.toString(addOne(new int[] { 9, 9, 9, 8 })));
					//
					//
					ArrayList<Integer> A = new ArrayList<Integer>();
					A.add(9);
					A.add(9);
					A.add(9);
					A.add(8);

					System.out.println("--------------------------");
					System.out.println(Arrays.toString(addOne1(A)));

				}

				public static int plusOne(ArrayList<Integer> A) {

					int sum = 0;
					String str = "";
					for (int i = 0; i <= A.size(); i++) {
						str += A.get(i);

					}
					sum = Integer.parseInt(str) + 1;

					return sum;
				}

				public static final int[] addOne(int[] digits) {
					int carry = 1;
					int[] result = new int[digits.length];
					for (int i = digits.length - 1; i >= 0; i--) {
						int val = digits[i] + carry;
						result[i] = val % 10;
						carry = val / 10;
					}
					if (carry == 1) {
						result = new int[digits.length + 1];
						result[0] = 1;
					}
					return result;
				}

				public static final int[] addOne1(ArrayList<Integer> A) {
					int carry = 1;
					int[] result = new int[A.size()];
					
					for (int i = A.size()-1; i >= 0; i--) {
						int val = A.get(i) + carry;
						result[i] = val % 10;
						carry = val / 10;
					}
					if (carry == 1) {
						result = new int[A.size()];
						result[0] = 1;
					}
					return result;
				}

			}

Algorithm-Java-programming- Arrays

My learning

balance-array

https://www.interviewbit.com/problems/balance-array/

package com.array;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * Given an integer array A of size N. You need to count the number of special
 * elements in the given array.
 * 
 * A element is special if removal of that element make the array balanced.
 * 
 * Array will be balanced if sum of even index element equal to sum of odd index
 * element.
 * 
 * 
 * @author vkhan
 *
 */
public class BalanceArrayonRemoval {

	public static void main(String args[]) {
		// [2, 1, 6, 4]
		// [5, 5, 2, 5, 8]
		Integer arr1[] = { 2, 1, 6, 4 };
		Integer arr2[] = { 5, 5, 2, 5, 8 };
		System.out.println(solve(Arrays.asList(arr1)));
		System.out.println(solve(Arrays.asList(arr2)));

	}

//Editorial
	static int solve(List<Integer> A) {

		if (A.size() == 1)
			return 1;

		int[] cumsum = new int[A.size()];
		int count = 0, evensum = 0, oddsum = 0, evenSumTot = 0, oddSumTot = 0;

		cumsum[0] = A.get(0);
		cumsum[1] = A.get(1);

		// cumsum[0, 2, 4, ...] are even sum and cumsum[1, 3, 5, ...] are odd sum
		for (int i = 2; i < A.size(); ++i)
			cumsum[i] = cumsum[i - 2] + A.get(i);

		// depending on size of input array the total odd sum and the total odd sum
		// will be in different position of cumsum array
		// eg n=5 then osumtot = (1,3) ie cumsum[n-2] ; esumtot = (0,2,4)()ie
		// cumsum[n-1]
		if (A.size() % 2 == 1) {
			oddSumTot = cumsum[A.size() - 2];
			evenSumTot = cumsum[A.size() - 1];
		} else // (A.size()%2==0)
		{
			oddSumTot = cumsum[A.size() - 1];
			evenSumTot = cumsum[A.size() - 2];
		}

		int pre;
		for (int i = 0; i < A.size(); ++i) {
			if (i == 0)
				pre = 0; // when considering removing first index we set previous sum to
							// be zero
			else
				pre = cumsum[i - 1];

			// iterate over each positon to find esum and osum when that index is removed
			if (i % 2 == 1)// if i is 0dd
			{
				evensum = pre + (oddSumTot - cumsum[i]);
				oddsum = cumsum[i] + (evenSumTot - pre) - A.get(i);
			} else// i is even
			{
				evensum = cumsum[i] + (oddSumTot - pre) - A.get(i);
				oddsum = pre + (evenSumTot - cumsum[i]);
			}

			if (evensum == oddsum)
				count++;
		}
		return count;
	}

//Fastest
	public int solve1(ArrayList<Integer> a) {
		if (a == null || a.size() == 2) {
			return 0;
		}

		if (a.size() == 1) {
			return 1;
		}

		int totalEven = 0;
		int totalOdd = 0;
		boolean even = true;
		for (int i = 0; i < a.size(); i++) {
			if (even) {
				totalEven += a.get(i);
			} else {
				totalOdd += a.get(i);
			}
			even = !even;
		}

		int lEven = 0;
		int rEven = 0;
		int lOdd = 0;
		int rOdd = 0;
		int count = 0;
		even = true;
		for (int i = 0; i < a.size(); i++) {
			if (even) {
				rEven = totalEven - lEven - a.get(i);
				rOdd = totalOdd - lOdd;
				if ((lEven + rOdd) == (lOdd + rEven)) {
					count++;
				}
				lEven += a.get(i);
			} else {
				rEven = totalEven - lEven;
				rOdd = totalOdd - lOdd - a.get(i);
				if ((lEven + rOdd) == (lOdd + rEven)) {
					count++;
				}
				lOdd += a.get(i);
			}

			even = !even;
		}

		return count;
	}

	// light weight
	public int solve3(ArrayList<Integer> A) {
		int n = A.size();
		long[][] dp = new long[n + 1][2];
		for (int i = n - 1; i >= 0; i--) {
			dp[i][1] = dp[i + 1][1];
			dp[i][0] = dp[i + 1][0];
			if (i % 2 == 1) {
				dp[i][0] += A.get(i);
			} else {
				dp[i][1] += A.get(i);
			}
		}
		int cnt = 0;
		long odd = 0;
		long even = 0;
		for (int i = 0; i < A.size(); i++) {
			long nextOdd = 0;
			long nextEven = 0;
			if (i % 2 == 1) {
				nextOdd = odd + dp[i][1];
				nextEven = even + dp[i][0] - A.get(i);
			} else {
				nextOdd = odd + dp[i][1] - A.get(i);
				nextEven = even + dp[i][0];
			}
			if (nextOdd == nextEven) {
				cnt++;
			}
			if (i % 2 == 1) {
				odd += A.get(i);
			} else {
				even += A.get(i);
			}
		}
		return cnt;
	}
}

big-sorting problem

https://www.hackerrank.com/challenges/big-sorting/problem

static String[] bigSorting(String[] unsorted) {
		if (null == unsorted)
			return unsorted;
		//
		Arrays.sort(unsorted, new Comparator<String>() {
			@Override
			public int compare(String o1, String o2) {
				// TODO Auto-generated method stub
				return compareStrings(o1, o2);// Integer.valueOf(o1).compareTo(Integer.valueOf(o2));
			}

		});
		for (String s : unsorted)
			System.out.println("number1=" + s);

		return unsorted;

	}

	private static int compareStrings(String s1, String s2) {
		//
		if (s1.length() < s2.length()) {
			return -1;
		} else if (s1.length() > s2.length()) {
			return 1;
		}
		for (int i = 0; i < s1.length(); i++) {
			if ((int) s1.charAt(i) < (int) s2.charAt(i))
				return -1;
			if ((int) s1.charAt(i) > (int) s2.charAt(i))
				return 1;

		}
		return 0;

	}


//Java 8

      Arrays.sort(unsorted, (left, right) -> {
			if (left.length() != right.length()) {
				return left.length() - right.length();
			} else {
				return left.compareTo(right);
			}
		});

BinarayreeRightSideView

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class BinarayreeRightSideView {

	public static void main(String[] args) {

	}

	public List<Integer> rightSideView(TreeNode root) {

		List<Integer> res = new ArrayList<Integer>();

		if (root == null) {
			return res;
		}
		//
		Queue<TreeNode> queue = new LinkedList<TreeNode>();
		queue.offer(root);
		// queue.remove(root);

		//
		while (!queue.isEmpty()) {
			TreeNode cur = queue.peek();
			int curSize = queue.size();
			for (int i = 0; i < curSize; i++) {

				cur = queue.poll();

				if (cur.left != null) {
					queue.offer(cur.left);
					// queue.add(cur.left);

				}
				if (cur.right != null) {
					queue.offer(cur.right);
					// queue.add(cur.right);

				}
			}
			res.add(cur.val);
		}
		return res;
	}
}

BuddyString

- https://leetcode.com/problems/buddy-strings/submissions/



          import java.util.ArrayList;
          import java.util.HashSet;
          import java.util.List;
          import java.util.Set;

          public class BuddyString {

            public static void main(String[] args) {
              String A = "aa";
              String B = "aa";
              System.out.println(buddyStrings(A, B));
            }

            public static boolean buddyStrings(String A, String B) {
              if (A.length() != B.length())
                return false;


              if (A.equals(B)) {
                Set<Character> set = new HashSet();
                for (char ch : A.toCharArray()) {
                  set.add(ch);
                }
                //if B size less means duplicate char
                //example in case A=aa b=aa its save a and return true
                //in case A=ab B=ab then store ab and condition return false
                return set.size() < A.length();
              }

              List<Integer> diff = new ArrayList();
              //if diff size is more then 2 means not swap 1 char
              for (int i = 0; i < A.length(); i++) {
                if (A.charAt(i) != B.charAt(i)) {
                  diff.add(i);
                  if (diff.size() > 2) {
                    return false;
                  }
                }
              }

              return diff.size() == 2 && A.charAt(diff.get(0)) == B.charAt(diff.get(1)) && A.charAt(diff.get(1)) == B.charAt(diff.get(0));
            }

            public static boolean buddyStrings1(String A, String B) {

              //
              if (null == A || A.isEmpty())
                return false;
              //
              if (null == B || B.isEmpty())
                return false;
              //
              if (A.length() != B.length()) {
                return false;
              } else {

                char arr1[] = A.toCharArray();
                char arr2[] = B.toCharArray();

                for (int i = 0; i < arr1.length; i++) {
                  if (A.charAt(i) == B.charAt(i)) {

                  }
                }
              }

              return false;
            }

          }

Count all distinct pairs with difference equal to k

//https://www.geeksforgeeks.org/count-pairs-difference-equal-k/
public class DiffrenceK {

	static int countPairsWithDiffK(int arr[], int k) {
		int count = 0;

    // Pick all elements one by one
		for (int i = 0; i < arr.length; i++) {
         // See if there is a pair of this picked element
			for (int j = i + 1; j < arr.length; j++)
				if (arr[i] - arr[j] == k || arr[j] - arr[i] == k) {
					count++;
				}
		}
		return count;
	}

   // Driver code
	public static void main(String args[]) {
		int arr[] = { 1, 5, 3, 4, 2 };
		int k = 3;
		System.out.println("Count of pairs with given diff is " + countPairsWithDiffK(arr, k));
	}
}

Count the Number of Consistent Strings

- https://leetcode.com/problems/count-the-number-of-consistent-strings/

        class Solution {
            public int countConsistentStrings(String allowed, String[] words) {
                  Map<Character, Integer> map = new HashMap();
                //Add all allowed char to map and count
                //since key overrite if get dupicate so no count needed
                for (char ch : allowed.toCharArray()) {
                  map.put(ch, 1);
                }
                //
                int count = 0;
                for (String str : words) {
                  // Add no matter what
                  count++;
                  //
                  for (char ch : str.toCharArray()) {
                    if (map.get(ch) == null) {
                      // Only if we find no match will we decrement and break loop
                      count--;
                      break;
                    }
                  }
                }
                return count;
            }
        }

Decode String

The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times. Note that k is guaranteed to be a positive integer.
You may assume that the input string is always valid; No extra white spaces, square brackets are well-formed, etc.
Furthermore, you may assume that the original data does not contain any digits and that digits are only for those repeat numbers, k. For example, there won’t be input like 3a or 2[4].
Examples:
s = "3[a]2[bc]", return "aaabcbc".
s = "3[a2[c]]", return "accaccacc".
s = "2[abc]3[cd]ef", return "abcabccdcdcdef".


			import java.util.Stack;

			public class StringDecoding {
				/**
				 * s = "3[a]2[bc]", return "aaabcbc".
				 * s = "3[a2[c]]", return "accaccacc".
				 * s = "2[abc]3[cd]ef", return "abcabccdcdcdef".
				 * 
				 * @param args
				 */
				public static void main(String[] args) {
					// TODO Auto-generated method stub
					String str = "3[a]2[bc]";
					System.out.println("result=" + decodeString1(str));
				}

				public static String decodeString1(String s) {
					if (s.length() == 0 || s == null) {
						return s;
					}
					Stack<String> strStack = new Stack<String>();
					Stack<Integer> numStack = new Stack<Integer>();
					StringBuilder res = new StringBuilder();
					int index = 0;
					//
					while (index < s.length()) {
						if (Character.isDigit(s.charAt(index))) {
							int num = 0;
							// if 32[a] will come then
							// num = 0 so 0*10+(3)
							// num=3
							// now come 2 so 3*10+2 =32
							// if 3 will come
							while (Character.isDigit(s.charAt(index))) {
								num = num * 10 + (s.charAt(index) - '0');
								index++;
							}
							numStack.push(num);
						} else if (s.charAt(index) == '[') {
							strStack.push(res.toString());
							res = new StringBuilder("");
							index++;
						} else if (s.charAt(index) == ']') {
							StringBuilder temp = new StringBuilder(strStack.pop());
							int repeatTimes = numStack.pop();
							for (int i = 0; i < repeatTimes; i++) {
								temp.append(res);
							}
							res = temp;
							index++;
						} else {
							res.append(s.charAt(index++));
						}
					}
					return res.toString();
				}

			}

Find Duplicate in Array

//https://www.interviewbit.com/problems/find-duplicate-in-array/
public ArrayList<Integer> repeatedNumber(final List<Integer> a) {
        
    	Int [] arr= {247, 240, 303, 9, 304, 105, 44, 204, 291, 26, 242, 2, 358, 264, 176, 289, 196, 329, 
    			189, 102, 45, 111, 115, 339, 74, 200, 34, 201, 215, 173, 107, 141, 71, 125, 6, 241, 275, 88, 
    			91, 58, 171, 346, 219, 238, 246, 10, 118, 163, 287, 179, 123, 348, 283, 313, 226, 324, 203, 
    			323, 28, 251, 69, 311, 330, 316, 320, 312, 50, 157, 342, 12, 253, 180, 112, 90, 16, 288, 213, 273,
    			 57, 243, 42, 168, 55, 144, 131, 38, 317, 194, 355, 254, 202, 351, 62, 80, 134, 321, 31, 127, 232, 67,
    			 22, 124, 271, 231, 162, 172, 52, 228, 87, 174, 307, 36, 148, 302, 198, 24, 338, 276, 327, 150, 110, 188, 
    			 309, 354, 190, 265, 3, 108, 218, 164, 145, 285, 99, 60, 286, 103, 119, 29, 75, 212, 290, 301, 151, 17,
    			 147, 94, 138, 272, 279, 222, 315, 116, 262, 1, 334, 41, 54, 208, 139, 332, 89, 18, 233, 268, 7, 214, 
    			 20, 46, 326, 298, 101, 47, 236, 216, 359, 161, 350, 5, 49, 122, 345, 269, 73, 76, 221, 280, 322,
    			 149, 318, 135, 234, 82, 120, 335, 98, 274, 182, 129, 106, 248, 64, 121, 258, 113, 349, 167, 192, 356,
    			 51, 166, 77, 297, 39, 305, 260, 14, 63, 165, 85, 224, 19, 27, 177, 344, 33, 259, 292, 100, 43, 314, 170, 
    			 97, 4, 78, 310, 61, 328, 199, 255, 159, 185, 261, 229, 11, 295, 353, 186, 325, 79, 142, 223, 211, 152, 266, 
    			 48, 347, 21, 169, 65, 140, 83, 156, 340, 56, 220, 130, 117, 143, 277, 235, 59, 205, 153, 352, 300, 114, 84, 
    			 183, 333, 230, 197, 336, 244, 195, 37, 23, 206, 86, 15, 187, 181, 308, 109, 293, 128, 66, 270, 209, 158, 32, 
    			 25, 227, 191, 35, 40, 13, 175, 146, 299, 207, 217, 281, 30, 357, 184, 133, 245, 284, 343, 53, 210, 306, 136, 
    			 132, 239, 155, 73, 193, 278, 257, 126, 331, 294, 250, 252, 263, 92, 267, 282, 72, 95, 337, 154, 319, 341, 70, 
    			 81, 68, 160, 8, 249, 96, 104, 137, 256, 93, 178, 296, 225, 237};
    	Arrays.asList(arr);
    	
    	ArrayList<Integer> res = new ArrayList<Integer>();
        int n = a.size();
        
        long sumOfNum = (((long) n) * ((long) n + 1)) / 2;
        long sumOfSq = (((long) n) * ((long) n + 1) * ((long) 2*n + 1)) / 6;
    
        for (int i=0; i < n; i++) {
            sumOfNum -= (long) a.get(i);
        }
 
        for (int i=0; i < n; i++) {
            sumOfSq -= (long) a.get(i) * (long) a.get(i);
        }
        
        long sumNum = sumOfSq/sumOfNum;
        
        int missing = (int) (sumNum + sumOfNum)/2;
        int repeated = (int) (sumNum - missing);
        
        res.add(repeated);
        res.add(missing);
        
        return res;
    }
}

Find Duplicate in String

package com;

import java.util.HashMap;
import java.util.Map;

public class DuplicateWordsString {

	public static void main(String[] args) {
		String str = "Hi i am vaquar khan and khan is good people";
		dubplicateFInd(str);

	}

	private static void dubplicateFInd(String str) {

		String[] str1 = str.split(" ");

		Map<String, Integer> map = new HashMap();
		// for (int i = 0; i < str1.length; i++) {
		for (String sr : str1) {
			//
			if (!map.containsKey(sr)) {
				map.put(sr, 1);
			} else {
				map.put(sr, map.get(sr) + 1);
			}
		}
		//print 
		for (Map.Entry<String, Integer> entry : map.entrySet()) {
			System.out.println(entry.getKey() + ":" + entry.getValue());
		}

	}

}

find the first missing positive integer

/*
Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the one that is missing from the array.
Example 1
Input: [3,0,1]
Output: 2
Example 2
Input: [9,6,4,2,3,5,7,0,1]
Output: 8
Note:
Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity?
*/

/**
 * Approach 1： HashSet 
 * Using a HashSet to get constant time containment queries and overall linear runtime.
 * Algorithm
 * We traverse the array nums and store the elements in the set.
 * Then we iterator the set, we can easily figure out which number is missing.
 * 
 * Complexity Analysis
 * Time complexity : O(n)
 * Because the set allows for O(1) containment queries, the main loop runs in O(n) time. 
 * Creating num_set costs O(n) time, as each set insertion runs in amortized O(1) time,
 * so the overall runtime is O(n+n) = O(n).
 * Space complexity : O(n)
 * nums contains n-1 distinct elements, so it costs O(n) space to store a set containing all of them.
 */
class Solution {
    public int missingNumber(int[] nums) {
        Set<Integer> numSet = new HashSet<Integer>();
        // store the elements in nums
        for (int num : nums) {
            numSet.add(num);
        }

        int expectedNumCount = nums.length + 1;
        // iterator the set to find the missing number
        for (int number = 0; number < expectedNumCount; number++) {
            if (!numSet.contains(number)) {
                return number;
            }
        }
        return -1;
    }
}

/**
 * Approach 2: Bit Manipulation 
 * Intuition
 * We can harness the fact that XOR is its own inverse to find the missing element in linear time.
 * Algorithm
 * Because we know that nums contains n numbers and that 
 * it is missing exactly one number on the range [0..n−1], 
 * we know that n definitely replaces the missing number in nums. 
 * Therefore, if we initialize an integer to n and XOR it with every index and value, 
 * we will be left with the missing number. 
 * 
 * Consider the following example 
 * (the values have been sorted for intuitive convenience, but need not be):
 *      Index   0   1   2   3
 *      Value   0   1   3   4
 *      missing = 4^(0^0)^(1^1)^(2^3)^(3^4)
 *              = (4^4)^(0^0)^(1^1)^(3^3)^2
 *              =0^0^0^0^2
 *              =2
 *              
 * Complexity Analysis
 * Time complexity : O(n)
 * Assuming that XOR is a constant-time operation, 
 * this algorithm does constant work on n iterations, so the runtime is overall linear.
 * Space complexity : O(1)
 * This algorithm allocates only constant additional space.
 */
class Solution {
    public int missingNumber(int[] nums) {
        int missing = nums.length;
        for (int i = 0; i < nums.length; i++) {
            missing ^= i ^ nums[i];
        }
        return missing;
    }
}

/**
 * Approach 3: Gauss' Formula
 * Intuition
 * One of the most well-known stories in mathematics is of a young Gauss, 
 * forced to find the sum of the first 100 natural numbers. 
 * Rather than add the numbers by hand, 
 * he deduced a closed-form expression for the sum. You can see the formula below:
 * ∑​ni=​n(n+1)/2
 * https://brilliant.org/wiki/sum-of-n-n2-or-n3/
 * 
 * Algorithm
 * We can compute the sum of nums in linear time, 
 * and by Gauss' formula, we can compute the sum of the first n natural numbers in constant time. 
 * Therefore, the number that is missing is simply the result of Gauss' formula minus the sum of nums, 
 * as nums consists of the first n natural numbers minus some number.
 * 
 * Complexity Analysis
 * Time complexity : O(n)
 * Although Gauss' formula can be computed in O(1) time, summing nums costs us O(n) time, 
 * so the algorithm is overall linear. 
 * Because we have no information about which number is missing, 
 * an adversary could always design an input for which any algorithm 
 * that examines fewer than n numbers fails. 
 * Therefore, this solution is asymptotically optimal.
 * Space complexity : O(1)
 * This approach only pushes a few integers around, so it has constant memory usage.
 */
class Solution {
    public int missingNumber(int[] nums) {
        int expectedSum = nums.length * (nums.length + 1) / 2;
        int actualSum = 0;
        for (int num : nums) {
            actualSum += num;
        }
        return expectedSum - actualSum;
    }
}

FirstNon Repeating Character in String

package com.array;


import java.util.LinkedHashMap;
import java.util.Map;

public class FirstNonRepeatingCharacterString {

	;

	// Driver method
	public static void main(String[] args) {
		String str = "geeksforgeeks";
		//
		char index = firstNonRepeating(str);
		
		System.out.println(index);

		//System.out.println(index == -1 ? "Either all characters are repeating or string " + "is empty"
			//	: "First non-repeating character is " + str.charAt(index));
	}

	/*
	 * The method returns index of first non-repeating character in a string. If all
	 * characters are repeating then returns -1
	 */
	static char firstNonRepeating(String str) {
		char arr[] = str.toCharArray();
		//
		int count=0;
		Map<Character,Integer> map = new LinkedHashMap();
		char val=' ';
		//
		for (int i = 0; i < str.length(); i++) {
			if(!map.containsKey(arr[i])) {
				map.put(arr[i], 1);
			}else {
				map.put(arr[i],map.get(arr[i])+1);

			}
		}

		//print 
				for (Map.Entry<Character, Integer> entry : map.entrySet()) {
					if(entry.getValue()==1) {
					System.out.println(entry.getKey() + ":" + entry.getValue());
					val=entry.getKey();
					break;
					}
				}

		return val;
	}

}

form the largest number

		import java.util.Arrays;
		import java.util.Comparator;

		Given a list of non negative integers, arrange them such that they form the largest number.

For example:

Given [3, 30, 34, 5, 9], the largest formed number is 9534330.

Note: The result may be very large, so you need to return a string instead of an integer.


    
    
    public class StringLargestNumber {

			public static void main(String[] args) {
				final int[] A = { 3, 30, 34, 5, 9 };// 9534330//3,5,9,30,34

				System.out.println(largestNumber(A));

			}

			public static String largestNumber(final int[] A) {
				String arr[] = new String[A.length];
				//
				for (int i = 0; i <= A.length - 1; i++) {
					arr[i] = String.valueOf(A[i]);
				}
				//
				Arrays.sort(arr, new Comparator<String>() {
					public int compare(String a, String b) {
						return (b + a).compareTo(a + b);
					}
				});

				StringBuilder sb = new StringBuilder();
				for (String s : arr) {
					sb.append(s);
				}

				while (sb.charAt(0) == '0' && sb.length() > 1) {
					sb.deleteCharAt(0);
				}
				return sb.toString();
			}
		}

gistfile1.txt

		//https://www.interviewbit.com/problems/pick-from-both-sides/
    
    package com.array;

		import java.util.Arrays;
		import java.util.List;

		public class PickFromBothSides {

			public static void main(String[] args) {
				Integer[] arr = { 5, -2, 3, 1, 2 };
				System.out.println(solve(Arrays.asList(arr), 3));

			}

			public static int solve(List<Integer> A, int B) {

				int n = A.size();

				int result = 0;

				for (int i = 0; i < B; i++) {
					result += A.get(i);
				}

				int sum = result;

				for (int i = 0; i < B; i++) {
					sum -= A.get(B - 1 - i);
					sum += A.get(n - 1 - i);

					result = Math.max(result, sum);
				}

				return result;

			}
		}

gistfile2.txt

- https://leetcode.com/problems/design-parking-system/


            /**
             * How Many Numbers Are Smaller Than the Current Number.
             * See {@link <a href ="https://leetcode.com/problems/how-many-numbers-are-smaller-than-the-current-number/">https://leetcode.com/problems/how-many-numbers-are-smaller-than-the-current-number/</a>}
             */
            final class HowManySmallerNumbers {


              public static void main (String args[] ) {
                int nums [] = {8,1,2,2,3};
                smallerNumbersThanCurrent(nums) ;

              }
              static int[]  smallerNumbersThanCurrent(final int[] nums) {
                    int max = 0;
                    //Step 1: Find max no in array
                    for (int i = 0; i < nums.length; i++) {
                        max = Math.max(max, nums[i]);
                    }
                    //Step 2  create new array and fill table count 
                    /**
                     * filling array 
                     * 8,1,2,2,3
                     * 
                     *  0   1   2   3   4   5  6   7   8  9
                     * -----------------------------------------
                     * | 0 |1  | 2 | 1 | 0 |0 |0  |0  |1  |0   |
                     * -----------------------------------------
                     * 
                     * <-----------------------------------
                     */
                    final int[] sum = new int[max + 1];
                    for (int i = 0; i < nums.length; i++) {
                        sum[nums[i]]++;
                    }

                    //Step 3: 
                    for (int i = 1; i < sum.length; i++) {
                        sum[i] += sum[i - 1];
                    }
                    //Step 4: 
                    for (int i = 0; i < nums.length; i++) {
                        if (nums[i] != 0) {
                            nums[i] = sum[nums[i] - 1];
                        }
                    }
                    return nums;

                }
            }

gistfile3.txt

https://www.lintcode.com/problem/920/

 public static boolean canAttendMeetings(List<Interval> intervals) {
		
    	int [] startInv=new int[intervals.size()];
    	int [] endInv=new int[intervals.size()];

           for(int i=0;i<intervals.size();i++) {
        	  //set value in two arra
        	   startInv[i]=  intervals.get(i).start;
        	   endInv[i]=  intervals.get(i).end;

           }
           // Sort Array
           Arrays.sort(startInv);
           Arrays.sort(endInv);
           //Compare
           
           for(int i=0;i<startInv.length-1;i++) {
        	   
        	   if(startInv[i+1] <endInv[i]) {
        		   return false;
        	   }
           }
           
    	return true;
    }
    
    static class Interval {
    	     int start, end;
    	     Interval(int start, int end) {
    	         this.start = start;
    	         this.end = end;
    	     }
			public int getStart() {
				return start;
			}
			public void setStart(int start) {
				this.start = start;
			}
			public int getEnd() {
				return end;
			}
			public void setEnd(int end) {
				this.end = end;
			}
    	     
    	 }
}

gistfile4.txt

https://leetcode.com/problems/valid-parentheses/submissions/

import java.util.ArrayDeque;
import java.util.Deque;

public class ValidParentheses2 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		System.out.println(isValidParentheses("(("));

	}

	public static boolean isValidParentheses(String s) {
		 Deque<Character> stack = new ArrayDeque();
		 
		 for(int i =0;i<s.length();i++) {
			 //push left parenthsis into stack 
			 
			 if(s.charAt(i)=='('|| s.charAt(i)=='{' || s.charAt(i)=='[') {
				 stack.push(s.charAt(i));
			 }else {
				 
				 if(!stack.isEmpty()) {
					 char c= stack.pop();
					 if( 
						 (c=='('  && s.charAt(i)==')') ||
						 (c=='['  && s.charAt(i)==']') ||
						 (c =='{' && s.charAt(i)=='}')
						 ){
						 return false;
					 }
					 
				 }
				 
			 }
		 }
		 return true;
 
	}

}

Google Coding Interview Question - Sum Of Two

package com.solution.sorting;

import java.util.HashSet;
import java.util.Set;

public class SumOfTwo2 {
	/**
	 * 
	 * A=[0,0,-5,30212] B=[-10,40,-3,9] v=-8
	 * 
	 * -5 + -3 = -8 subOfTwo(a,b,v)= true
	 * 
	 * @param args
	 */
	public static void main(String[] args) {
		int a[] = { 0, 0, -5, 30212 };
		int b[] = { -10, 40, -3, 9 };
		int v = -8;

		twoSum(a, b, v);
		twoSum1(a, b, v);

	}
	// O(n*n)

	public static boolean twoSum(int[] a, int[] b, int v) {

		for (int i = 0; i < a.length; i++) {
			for (int j = 0; j < b.length; j++) {
				if ((a[i] + b[i]) == v) {
					System.out.println(a[i] + b[i]);
					return true;

				}

			}
		}

		return false;
	}

	// O(n)
	public static boolean twoSum1(int[] a, int[] b, int v) {

		Set<Integer> set = new HashSet();

		for (int i = 0; i < a.length; i++) {
			set.add(v - a[i]);
		}

		for (int j = 0; j < b.length; j++) {
			if (set.contains(b[j])) {
				System.out.println(b[j]);

				return true;
			}
		}

		return false;
	}

}

group-anagrams

//https://leetcode.com/problems/group-anagrams/submissions/
package com;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * Input: strs = ["eat","tea","tan","ate","nat","bat"] Output:
 * [["bat"],["nat","tan"],["ate","eat","tea"]]
 * 
 * Example 2:
 * 
 * Input: strs = [""] Output: [[""]]
 * 
 * Example 3:
 * 
 * Input: strs = ["a"] Output: [["a"]]
 * 
 *
 * 
 */
public class Anagrams1 {

	public static void main(String[] args) {

		String[] strs = { "eat", "tea", "tan", "ate", "nat", "bat" };
		List<List<String>> list = groupAnagrams(strs);
		for (List li : list) {
			System.out.println(li);

		}

	}

	public static  List<List<String>> groupAnagrams(String[] strs) {
		Map<String, List<String>> map = new HashMap<>();
		//
		for (String word : strs) {
			char[] c = word.toCharArray();
			//
			Arrays.sort(c);
			//System.out.println("=C="+c.toString());

			String hash = new String(c);
			//System.out.println("=contain=hash="+hash);

			//
			if (map.containsKey(hash)) {
				map.get(hash).add(word);
			} else {
				//
				List<String> list = new ArrayList<>();
				list.add(word);
				map.put(hash, list);
			}
		}

		return new ArrayList<List<String>>(map.values());
	}
}

Hotel Bookings Possible

https://www.interviewbit.com/problems/hotel-bookings-possible/

import java.util.ArrayList;
import java.util.Collections;

public class HotelBookingsPossibl {

	public static void main(String[] args) {
		ArrayList<Integer> arrive = new ArrayList<Integer>();
		arrive.add(1);
		arrive.add(3);
		arrive.add(5);

		ArrayList<Integer> depart = new ArrayList<Integer>();
		depart.add(2);
		depart.add(6);
		depart.add(8);
		int K = 1;
		System.out.println(hotel(arrive,depart,K));
	}

	public static boolean hotel(ArrayList<Integer> arrive, ArrayList<Integer> depart, int K) {

		if (null == arrive || arrive.isEmpty())
			return false;
		if (null == depart || depart.isEmpty())
			return false;
		if (K == 0)
			return false;
		// both list sort
		Collections.sort(arrive);
		Collections.sort(depart);
		//
		int n = arrive.size();
		int currBookingCount = 1;
		int maxBookingCount = 1;
		int arriveIdx = 1;
		int departIdx = 0;
		//
		while (arriveIdx < n && departIdx < n) {
			if (arrive.get(arriveIdx) < depart.get(departIdx)) {
				currBookingCount++;
				maxBookingCount = Math.max(maxBookingCount, currBookingCount);
				arriveIdx++;

			} else {
				currBookingCount--;
				departIdx++;
			}
			if (maxBookingCount > K) {
				return false;
			}
		}

		return true;
	}
}

Longest Substring Without Repeating Characters

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        if (s == null || s.length() == 0){
            return 0;
        }
        int max = 1;
        int start = 0;
        int end = 1;
        HashMap<Character, Integer> map = new HashMap<Character, Integer>();
        map.put(s.charAt(0), 0);
        while (end < s.length()){
            char c = s.charAt(end);
            if (map.containsKey(c) && map.get(c) >= start){
                start = map.get(c) + 1;
            }
            map.put(c, end);
            max = Math.max(max, end - start + 1);
            end++;
        }
        return max;
    }
}

max-sum-contiguous-subarray

https://www.interviewbit.com/problems/max-sum-contiguous-subarray/


				public int maxSubArray(final List<Integer> A){
					int currMax = A.get(0);
					int tempMax = A.get(0);
					for(int i=1;i<A.size();i++){
						if(A.get(i)>tempMax+A.get(i)){
							tempMax=A.get(i);
						}
						else{
							tempMax+=A.get(i);
						}
						if(currMax < tempMax){
							currMax=tempMax;
						}
					}
					return currMax;
				}


			================
			public int maxSubArray(final List<Integer> A){
					int currMax = A.get(0);
					int tempMax = A.get(0);
					for(int i=1;i<A.size();i++){
						if(A.get(i)>tempMax+A.get(i)){
							tempMax=A.get(i);
						}
						else{
							tempMax+=A.get(i);
						}
						if(currMax < tempMax){
							currMax=tempMax;
						}
					}
					return currMax;
				}

			===============

				public int maxSubArray(final List<Integer> A) {
					int maxEndingHere = A.get(0);
					int maxSoFar = A.get(0);
					for (int i = 1; i < A.size(); i++) {
						maxEndingHere = Math.max(A.get(i), A.get(i) + maxEndingHere);
						maxSoFar = Math.max(maxSoFar, maxEndingHere);
					}
					return maxSoFar;
				}

Maximum Consecutive Gap

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class MaximumConsecutiveGap {
	/**
	 * Input : [1, 10, 5] Output : 5
	 * 
	 * @param args
	 */
	public static void main(String[] args) {

		int arr[] = { 1, 10, 5 };
		final List<Integer> A = new ArrayList();
		A.add(1);
		A.add(10);
		A.add(5);

		System.out.println(maximumGap(A));
	}

	public static int maximumGap(final List<Integer> A) {

		if (null == A || A.isEmpty())
			return 0;

		if (A.size() == 2)
			return 0;

		// Find maximum and minimum in arr[]

		Collections.sort(A);
		//
		int max = 0;
		for (int i = 0; i < A.size() - 1; i++) {
			if (A.get(i + 1) - A.get(i) > max)
				max = A.get(i + 1) - A.get(i);
		}
		return max;

	}
}

maximum-absolute-difference

https://www.interviewbit.com/problems/maximum-absolute-difference/

Median Of Two Sorted Array

	public static double findMedianSortedArrays(int[] ar1, int[] ar2) {
		int[] result = new int[ar1.length + ar2.length];
		double medianVal = 0;
		//
		mergeArray(result, ar1, ar2);
		//
		int median = ar1.length + ar2.length;
		if (median % 2 == 0) {
			//
			medianVal = (double) ((result[(median / 2) - 1] + result[median / 2])) / 2;
			//
			System.out.println(medianVal);
		} else {
			medianVal = result[median / 2];
			System.out.println(medianVal);
		}
		return medianVal;
	}

	static void mergeArray(int[] result, int[] a, int[] b) {
		int first = 0;
		int second = 0;
		//
		for (int i = 0; i < a.length + b.length; i++) {
			if (first < a.length && second < b.length)
				if (a[first] < b[second]) {
					result[i] = a[first];
					first++;
				} else {
					result[i] = b[second];
					second++;
				}
			else {
				if (second == b.length && first < a.length) {
					result[i] = a[first];
					first++;
				}
				if (first == a.length && second < b.length) {
					result[i] = b[second];
					second++;
				}
			}
		}
	}

min-steps-in-infinite-grid

https://www.interviewbit.com/problems/min-steps-in-infinite-grid/

			import java.util.ArrayList;

			public class CoverPoints {

				public static void main(String[] args) {
					ArrayList<Integer> x = new ArrayList<>();
					x.add(0);
					x.add(1);
					x.add(1);

					ArrayList<Integer> y = new ArrayList<>();
					y.add(0);
					y.add(1);
					y.add(2);

					System.out.println(coverPoints(x, y));

				}

				public static int coverPoints(ArrayList<Integer> A, ArrayList<Integer> B) {
					//
					int count = 0;

					for (int i = 1; i < A.size(); i++) {
						//
						int x = Math.abs(A.get(i) - A.get(i - 1));
						int y = Math.abs(B.get(i) - B.get(i - 1));
						// count += (x >= y) ? x : y;

						if (x >= y) {
							count += x;
						} else {
							count += y;

						}
						//
					}
					return count;
				}
			}

MY Algorithms

605. Can Place Flowers
- https://leetcode.com/problems/can-place-flowers/submissions/


      class Solution {
          public boolean canPlaceFlowers(int[] flowerbed, int n) {

              int count = 0;
              for(int i = 0; i < flowerbed.length && count < n; i++) {
                  if(flowerbed[i] == 0) {
             //get next and prev flower bed slot values. If i lies at the ends the next and prev 
             //are considered as 0. 
                     int next = (i == flowerbed.length - 1) ? 0 : flowerbed[i + 1]; 
                     int prev = (i == 0) ? 0 : flowerbed[i - 1];
                     
                     if(next == 0 && prev == 0) {
                         flowerbed[i] = 1;
                         count++;
                     }
                  }
              }

              return count == n;

          }
      }

Noble Integer

Problem Description

Given an integer array A, find if an integer p exists in the array such that the number of integers greater than p in the array equals to p.



Input Format
First and only argument is an integer array A.



Output Format
Return 1 if any such integer p is found else return -1.



Example Input
Input 1:

 A = [3, 2, 1, 3]
Input 2:

 A = [1, 1, 3, 3]


Example Output
Output 1:

 1
Output 2:

 -1



import java.util.ArrayList;
import java.util.Collections;

public class NextPermutation {

	public static void main(String[] args) {
		//A = [3, 2, 1, 3]
		ArrayList<Integer> a = new ArrayList<Integer>();
		a.add(3);
		a.add(2);
		a.add(1);
		a.add(3);
		System.out.println(solve(a));
		
	}

	public static int solve(ArrayList<Integer> A) {

		if (null == A || A.isEmpty())
			return 0;

		Collections.sort(A);

		int idx = 0;
		int n = A.size();

		while (idx < n) {
			int num = A.get(idx);
			while (idx < n && A.get(idx) == num) {
				idx++;
			}
			if (num == A.size() - idx) {
				return 1;
			}

		}

		return -1;

	}

}

Powx -n

package com.array;

public class PowXN {
	/**
	 * https://leetcode.com/problems/powx-n/
	 * 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
	 * 
	 * @param args
	 */
	public static void main(String[] args) {
		//slow call
		System.out.println(pow(2.00000, 10));
		System.out.println(pow(2.10000, 3));
		System.out.println(pow(2.00000, -2));
		//
		System.out.println("-----------------------------------");
		//fast call
		PowXN pwn=new PowXN();
		System.out.println(pwn.pow1(2.00000, 10));
		System.out.println(pwn.pow1(2.10000, 3));
		System.out.println(pwn.pow1(2.00000, -2));
	}

	// Slow
	public static double pow(double x, int n) {
		double pow = 0;
		double multiply = 1;
		if (0 == x)
			return x;
		//
		if (n >= 0) {
			for (int i = 0; i < n; i++) {
				multiply = multiply * x;
			}
			pow = multiply;
		} else {
			for (int i = 0; i < n * (-1); i++) {
				multiply = multiply * x;
			}
			pow = 1 / multiply;
		}

		return pow;
	}

	// fast
	public double pow1(double x, int n) {
		if (n >= 0) {
			return mypow(x, n);
		}

		return 1 / mypow(x, n);

	}

	double mypow(double x, int n) {

		if (n == 0) {
			return 1;
		}

		double num = mypow(x, n / 2);

		if (n % 2 == 0) {
			return num * num;
		}

		return num * num * x;
	}

}

Remove duplicate

package com.array.function;

import java.util.Arrays;

public class RemoveDuplicate {
	/*
	 * consecutive Input : geeksforgeeks Output : geksforgeks
	 * 
	 */
	static void removeDuplicates(char[] S)  
    { 
        int n = S.length; 
  
        // We don't need to do anything for 
        // empty or single character string. 
        if (n < 2)  
        { 
            return; 
        } 
  
        // j is used to store index is result 
        // string (or index of current distinct 
        // character)  
        int j = 0; 
  
        // Traversing string  
        for (int i = 1; i < n; i++)  
        { 
            // If current character S[i] 
            // is different from S[j] 
            if (S[j] != S[i])  { 
                j++; 
                S[j] = S[i]; 
                /**
                 * e e k s f o r g e e k s =J
                 * g e e k s f o r g e e k s =i
                 */
            } 
        } 
        //
        for(Character s:S)
        System.out.println("S="+s);
        System.out.println("j+1="+j);

        System.out.println(Arrays.copyOfRange(S, 0, j + 1)); 
        
     } 
  

  
    // Driver code 
    public static void main(String[] args) 
    { 
        char S1[] = "geeksforgeeks".toCharArray(); 
        removeDuplicates(S1); 
  
        char S2[] = "aabcca".toCharArray(); 
        removeDuplicates(S2); 
        
        
        
    } 
} 

Roman-numerals

https://www.geeksforgeeks.org/converting-decimal-number-lying-between-1-to-3999-to-roman-numerals/

import java.util.Map;
import java.util.TreeMap;

public class RomanNumber {

	private final static TreeMap<Integer, String> map = new TreeMap<Integer, String>();

	static {

		map.put(1000, "M");
		map.put(900, "CM");
		map.put(500, "D");
		map.put(400, "CD");
		map.put(100, "C");
		map.put(90, "XC");
		map.put(50, "L");
		map.put(40, "XL");
		map.put(10, "X");
		map.put(9, "IX");
		map.put(5, "V");
		map.put(4, "IV");
		map.put(1, "I");

	}

	public final static String toRoman(int number) {
		int key = map.floorKey(number);
		//
		if (number == key) {
			return map.get(number);
		}
		return map.get(key) + toRoman(number - key);
	}

	public static void main(String args[]) {
		for (int i = 1; i <= 100; i++) {
			System.out.println(i + "\t =\t " + RomanNumber.toRoman(i));
		}
		//==================================
		System.out.println("==="+toRoman(1904));

	}
}

Rotate Image

import java.util.Arrays;

/**
 * 
 * {1,2,3},
 * {4,5,6},
 * {7,8,9}
 * 
 * [7, 4, 1]
 * [8, 5, 2]
 * [9, 6, 3]
 *
 * 
 * 
 */
public class RotateImage {

	public static void main(String[] args) {
		// int[][] multiples = new int[4][2];// 4 rows 2 column
		int[][] matrix = // new int[3][3];
				{ { 1, 2, 3 }, { 4, 5, 6 }, { 7, 8, 9 } };

		rotate(matrix);

	}

	public static void rotate(int[][] matrix) {
		
		if (matrix == null || matrix.length == 0 || matrix[0] == null || matrix[0].length == 0) {
			return;
		}
		int row = matrix.length;
		int col = matrix[0].length;
		//
		for (int i = 0; i < row / 2; i++) {
			for (int j = 0; j < col; j++) {
				swap(matrix, i, j, row - 1 - i, j);
			}
		}
		//[1,2,3],
		//[4,5,6],
		//[7,8,9]
		//
		//[7, 8, 9],
		//[4, 5, 6],
		//[1, 2, 3]
		//
		for (int i = 0; i < row; i++) {
			for (int j = i + 1; j < col; j++) {
				swap(matrix, i, j, j, i);
			}
		}
		//[7, 4, 1]
		//[8, 5, 2]
		//[9, 6, 3]
		System.out.println("2="+Arrays.deepToString(matrix));

	}

	private static void swap(int[][] matrix, int x0, int y0, int x1, int y1) {
		int temp = matrix[x0][y0];
		matrix[x0][y0] = matrix[x1][y1];
		matrix[x1][y1] = temp;
	}
}

// /*
//  * clockwise rotate
//  * first reverse up to down, then swap the symmetry 
//  * 1 2 3     7 8 9     7 4 1
//  * 4 5 6  => 4 5 6  => 8 5 2
//  * 7 8 9     1 2 3     9 6 3
// */
// void rotate(vector<vector<int> > &matrix) {
//     reverse(matrix.begin(), matrix.end());
//     for (int i = 0; i < matrix.size(); ++i) {
//         for (int j = i + 1; j < matrix[i].size(); ++j)
//             swap(matrix[i][j], matrix[j][i]);
//     }
// }

// /*
//  * anticlockwise rotate
//  * first reverse left to right, then swap the symmetry
//  * 1 2 3     3 2 1     3 6 9
//  * 4 5 6  => 6 5 4  => 2 5 8
//  * 7 8 9     9 8 7     1 4 7
// */
// void anti_rotate(vector<vector<int> > &matrix) {
//     for (auto vi : matrix) reverse(vi.begin(), vi.end());
//     for (int i = 0; i < matrix.size(); ++i) {
//         for (int j = i + 1; j < matrix[i].size(); ++j)
//             swap(matrix[i][j], matrix[j][i]);
//     }
// }

Rotate image ArrayList

static void rotate(ArrayList<ArrayList<Integer>> a) {

		if (null != a && !a.isEmpty())
			return;
		//
		int N = a.size() - 1;
		//
		for (int i = 0; i < a.size() / 2; i++) {
			for (int j = i; j < N - i; j++) {
				int temp1 = a.get(N - j).get(i);
				int temp2 = a.get(N - i).get(N - j);
				int temp3 = a.get(j).get(N - i);
				int temp4 = a.get(i).get(j);

				a.get(i).set(j, temp1);
				a.get(N - j).set(i, temp2);
				a.get(N - i).set(N - j, temp3);
				a.get(j).set(N - i, temp4);
			}
		}
	}

	public static void main(String[] args) {
		ArrayList<ArrayList<Integer>> A = new ArrayList<ArrayList<Integer>>();

		ArrayList<Integer> temp = new ArrayList<Integer>();
		temp.add(1);
		temp.add(2);
		temp.add(3);
		temp.add(4);
		A.add(new ArrayList<Integer>(temp));
		temp.clear();

		temp.add(5);
		temp.add(6);
		temp.add(7);
		temp.add(8);
		A.add(new ArrayList<Integer>(temp));
		temp.clear();

		temp.add(9);
		temp.add(10);
		temp.add(11);
		temp.add(12);
		A.add(new ArrayList<Integer>(temp));
		temp.clear();

		temp.add(13);
		temp.add(14);
		temp.add(15);
		temp.add(16);
		A.add(new ArrayList<Integer>(temp));
		temp.clear();
		for (ArrayList<Integer> t : A)
			System.out.println(t);

		rotate(A);
	}

}

smallest-string-which-not-a-subsequence

import java.util.HashSet;
//https://www.geeksforgeeks.org/smallest-string-which-not-a-subsequence-of-the-given-string/
public class SubSequenceString {

	static String ShortestSubsequenceNotPresent(String str) {
		// Stores the shortest string which is not a subsequence of the given string
		String shortestString = "";

		// Stores length of string
		int N = str.length();

		// Stores distinct character of subsegments
		HashSet<Character> subsegments = new HashSet<>();

		// Traverse the given string
		for (int i = 0; i < N; i++) {

			// Insert current character
			// into subsegments
			subsegments.add(str.charAt(i));

			// If all lowercase alphabets present in the subsegment
			if (subsegments.size() == 26) {
				// Insert the last character of
				// subsegment into shortestString
				shortestString = shortestString + str.charAt(i);
				// Remove all elements from
				// the current subsegment
				subsegments.clear();
			}
		}

		// Traverse all lowercase alphabets
		for (char ch = 'a'; ch <= 'z'; ch++) {

			// If current character is not
			// present in the subsegment
			if (!subsegments.contains(ch)) {
				shortestString = shortestString + ch;

				// Return shortestString
				return shortestString;
			}
		}
		return shortestString;
	}

	// Driver Code
	public static void main(String[] args) {
		String str = "abcdefghijklmnopqrstuvwxyzaabbccdd";

		System.out.println(ShortestSubsequenceNotPresent(str));
		//System.out.println(ShortestSubsequenceNotPresent("abaabcc"));
		//sSystem.out.println(ShortestSubsequenceNotPresent("a"));

	}
}

Super Reduced String

// Complete the superReducedString function below.
    static String superReducedString(String s) {
char[] ch = s.toCharArray();
        
        Stack<Character> st = new Stack<Character>();
        //
        for (int i = 0; i < ch.length; i++) {
            if (st.empty()) {
                st.push(ch[i]);

            } else if (st.peek() == ch[i]) {
                st.pop();
            } else {
                st.push(ch[i]);

            }
        }
        //
        String str = "";
        while (!st.isEmpty()) {
            str = st.pop() + str;
        }
        return str==""?"Empty String" :str;

    }

Third Maximum Number

- https://leetcode.com/problems/third-maximum-number/

/**
 * 414. Third Maximum Number
 *
 * Given a non-empty array of integers, return the third maximum number in this array.
 * If it does not exist, return the maximum number. The time complexity must be in O(n).
 Example 1:
 Input: [3, 2, 1]
 Output: 1
 Explanation: The third maximum is 1.
 Example 2:
 Input: [1, 2]
 Output: 2
 Explanation: The third maximum does not exist, so the maximum (2) is returned instead.
 Example 3:
 Input: [2, 2, 3, 1]
 Output: 1
 Explanation: Note that the third maximum here means the third maximum distinct number.
 Both numbers with value 2 are both considered as second maximum.
 */
public class _414 {

    public int thirdMax(int[] nums) {
        long max1 = Long.MIN_VALUE;
        long max2 = Long.MIN_VALUE;
        long max3 = Long.MIN_VALUE;
        for (int i : nums) {
            max1 = Math.max(max1, i);
        }
        for (int i : nums) {
            if (i == max1) {
                continue;
            }
            max2 = Math.max(max2, i);
        }
        for (int i : nums) {
            if (i == max1 || i == max2) {
                continue;
            }
            max3 = Math.max(max3, i);
        }
        return (int) (max3 == Long.MIN_VALUE ? max1 : max3);
    }

}

Transpose Matrix

			import java.util.Arrays;

			public class TransposeMatrix {

				/**
				 * [1 2 3]
				 * [4 5 6]
				 * [7 8 9]
				 * Transpose Matrix
				 * [1 4 7]
				 * [2 5 8]
				 * [3 6 9]
				 * @param args
				 */
				public static void main(String[] args) {
					//int[][] multiples = new int[4][2];// 4 rows 2 column
					int[][] matrix = //new int[3][3];
						{
								{1,2,3},
								{4,5,6},
								{7,8,9}	
						};
					
					
					int[][] arr = transpose(matrix);
					//
						
					 System.out.println(Arrays.deepToString(arr));
				}

				static int [][] transpose(int [][] A){
					int row =A.length;
					int column=A[0].length;		
					//swap
					int newMatrix[][]= new int[column][row];
					
					for(int i=0;i<row;i++) {
						for(int j=0;j<column;j++) {
							//System.out.println(A[i][j]);
							newMatrix[j][i]=A[i][j];	
						}
					}
					return newMatrix;
					
				}
				
				static int[][] transpose1(int[][] A) {
					int row = A.length;
					int column = A[0].length;
					
					int[][] newMatrix = new int[column][row];
					//
					for (int r = 0; r < row; ++r)
						for (int c = 0; c < column; ++c) {
							newMatrix[c][r] = A[r][c];
						}
					return newMatrix;
				}

			}

wave-array

https://www.interviewbit.com/problems/wave-array/


import java.util.ArrayList;
import java.util.Collections;

public class WaveArray {

	public static void main(String[] args) {
		// 1, 2, 3, 4
		ArrayList<Integer> list = new ArrayList();
		list.add(1);
		list.add(2);
		list.add(3);
		list.add(4);
		//
		//One possible answer     : [2, 1, 4, 3]
		//Another possible answer : [4, 1, 3, 2]

		System.out.println(wave(list).toString());

	}
   //a1 >= a2 <= a3 >= a4 <= a5.
	public static ArrayList<Integer> wave(ArrayList<Integer> A) {

		if (null != A && A.isEmpty())
			return A;
		//
		Collections.sort(A);
		//
		for (int i = 0; i < A.size()-1; i+=2) {
		      
			 int temp = A.get(i);
		      A.set(i, A.get(i + 1));
		      A.set(i + 1, temp);

		}
		//
		return A;

	}

}

ZZZZ-others

- https://gist.github.com/nickmyself
- https://tenderleo.gitbooks.io/leetcode-solutions-/content
- https://gist.github.com/BiruLyu
- https://github.com/gouthampradhan/leetcode
- https://github.com/fluency03/leetcode-java
- https://www.codebycase.com/algorithms/a02-arrays-and-strings.html