Author: Shiva Charan Devabhaktuni

Using a Stack
Uses O(n) memory and time.

public class Solution {
    public String reverseWords(String s) {
        s = s.trim();
        Stack<String> track = new Stack<String>();
        String word = "";
        int i=0;
        while (i < s.length()) {
            if (s.charAt(i) == ' ') {
                track.push(word);
                word = "";
                while(i<s.length() && s.charAt(i) == ' ')
                    i++;
                continue;
            }
            word +=s.charAt(i++);
        }
        if (word != "") {
            track.push(word);
        }
        s = "";
        while(!track.isEmpty()) {
            s+= track.pop()+" ";
        }
        
        return s.trim();
    }
}

This solution runs in 0(n) time (linear) and uses O(1) space (constant) and is based on the Dutch National Flag Problem.

class Solution {
    public int[] sortArrayByParity(int[] A) {
        int low = 0, mid = 0, high = A.length - 1;
        int temp;
        while (mid <= high) {
            if (A[mid] == 0) {
                temp = A[mid];
                A[mid] = A[low];
                A[low] = temp;
                low++;
                mid++;
            } else if (A[mid] % 2 == 0) {
                mid++;
            } else {
                temp = A[mid];
                A[mid] = A[high];
                A[high] = temp;
                high--;
            }
        }
        return A;
    }
}

Optimized for runtime.
Time O(n)
Memory O(n)

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] ret = new int[2];
        HashMap < Integer, Integer > map = new HashMap < Integer, Integer > ();
        for (int i = 0; i < nums.length; i++) {
            if (map.get(nums[i]) != null) {
                ret[0] = map.get(nums[i]);
                ret[1] = i;
                return ret;
            }
            map.put(target - nums[i], i);
        }
        return ret;
    }
}

class Solution {
 public int myAtoi(String str) {
  int ret = 0;
  int i = 0;
  boolean negative = false;
  String retString = "";
  // Without using trim()
  // while(i<str.length() && str.charAt(i) == ' ')
  //     i++;
  str = str.trim();
  if (i >= str.length() || Character.isLetter(str.charAt(i)))
   return ret;
  if (str.charAt(i) == '-') {
   negative = true;
   i++;
  } else if (str.charAt(i) == '+') {
   i++;
  }
  while (i < str.length() && Character.isDigit(str.charAt(i))) {
   retString += str.charAt(i++);
  }
  if (retString != "") {
   try {
    ret = (negative ? -1 * Integer.parseInt(retString) : Integer.parseInt(retString));
   } catch (Exception e) {
    ret = (negative ? Integer.MIN_VALUE : Integer.MAX_VALUE);
   }
  }
  return ret;
 }
}

Time – O(n)
Space – 0(1)  – Neglecting the output array that is expected to be returned.

class Solution {
 public int[] productExceptSelf(int[] nums) {
  int n = nums.length;
  int[] output = new int[n];
  int temp = 1;
  // product from left to right excluding nums[i]
  for (int i = 0; i < n; i++) {
   output[i] = temp;
   temp *= nums[i];
  }
  temp = 1;
  // product from right to left excluding nums[i]
  for (int i = n - 1; i >= 0; i--) {
   output[i] *= temp;
   temp *= nums[i];
  }
  return output;
 }
}

This method doesn’t use a HashMap.

/**
 * Definition for singly-linked list with a random pointer.
 * class RandomListNode {
 *     int label;
 *     RandomListNode next, random;
 *     RandomListNode(int x) { this.label = x; }
 * };
 */
public class Solution {
 public RandomListNode copyRandomList(RandomListNode head) {
  if (head == null)
   return null;
  // Step 1 - Store copy in next
  RandomListNode n = head;
  while (n != null) {
   RandomListNode c = new RandomListNode(n.label);
   c.next = n.next;
   n.next = c;
   n = c.next;
  }
  // Step 2 - Copy Random reference
  n = head;
  while (n != null) {
   if (n.random != null) {
    n.next.random = n.random.next;
   }
   n = n.next.next;
  }
  // Step 3 - Break references
  n = head;
  RandomListNode ret = head.next;
  while (n != null) {
   RandomListNode copy = n.next;
   n.next = copy.next;
   if (n.next != null) {
    copy.next = n.next.next;
   }
   n = n.next;
  }
  return ret;
 }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
 public void flatten(TreeNode root) {
  moveLeftToRight(root);
 }

 public TreeNode moveLeftToRight(TreeNode root) {
  if (root == null)
   return null;
  TreeNode last = null;
  TreeNode right = root.right;
  if (root.left != null) {
   root.right = root.left;
   root.left = null;
   last = moveLeftToRight(root.right);
   last.right = right;
  }
  if (right != null) {
   last = moveLeftToRight(right);
  }
  return (last != null ? last : root);
 }
}