/**
 * 9. Palindrome Number
 * <p>
 * Determine whether an integer is a palindrome. An integer is a palindrome when it reads the same backward as forward.
 * <p>
 * Example 1:
 * <p>
 * Input: 121
 * Output: true
 * Example 2:
 * <p>
 * Input: -121
 * Output: false
 * Explanation: From left to right, it reads -121. From right to left, it becomes 121-. Therefore it is not a palindrome.
 * Example 3:
 * <p>
 * Input: 10
 * Output: false
 * Explanation: Reads 01 from right to left. Therefore it is not a palindrome.
 * Follow up:
 * <p>
 * Coud you solve it without converting the integer to a string?
 */
public class PalindromeNumber {
	public boolean isPalindrome(int x) {
		//for negative number no need to test
		if (x < 0) {
			return false;
		}

		int temp = x;

		int reverseNumber = 0;
		while (Math.abs(temp) > 0) {
			reverseNumber = reverseNumber * 10 + temp % 10;
			temp = temp / 10;
		}

		return reverseNumber == x;
	}
}

/**
 * 876. Middle of the Linked List
 * <p>
 * Given a non-empty, singly linked list with head node head, return a middle node of linked list.
 * <p>
 * If there are two middle nodes, return the second middle node.
 * <p>
 * Example 1:
 * <p>
 * Input: [1,2,3,4,5]
 * Output: Node 3 from this list (Serialization: [3,4,5])
 * The returned node has value 3.  (The judge's serialization of this node is [3,4,5]).
 * Note that we returned a ListNode object ans, such that:
 * ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, and ans.next.next.next = NULL.
 * Example 2:
 * <p>
 * Input: [1,2,3,4,5,6]
 * Output: Node 4 from this list (Serialization: [4,5,6])
 * Since the list has two middle nodes with values 3 and 4, we return the second one.
 */
public class MiddleNodeOfLinkedList {
	public ListNode middleNode(ListNode head) {

		ListNode slowPtr = head;
		ListNode fastPtr = head;

		while (fastPtr != null && fastPtr.next != null) {
			slowPtr = slowPtr.next;
			fastPtr = fastPtr.next.next;
		}

		return slowPtr;
	}
}

/**
 * 3. Longest Substring Without Repeating Characters
 * <p>
 * Given a string, find the length of the longest substring without repeating characters.
 * <p>
 * Example 1:
 * <p>
 * Input: "abcabcbb"
 * Output: 3
 * Explanation: The answer is "abc", with the length of 3.
 * Example 2:
 * <p>
 * Input: "bbbbb"
 * Output: 1
 * Explanation: The answer is "b", with the length of 1.
 * Example 3:
 * <p>
 * Input: "pwwkew"
 * Output: 3
 * Explanation: The answer is "wke", with the length of 3.
 * Note that the answer must be a substring, "pwke" is a subsequence and not a substring.
 */
public class LongestSubStrWithoutRepChars {
	public int lengthOfLongestSubstring(String s) {
		//base case
		if (s == null || s.length() == 0) {
			return 0;
		}

		Set<Character> set = new HashSet<>();
		int left = 0;
		int right = 0;
		int max = 0;

		while (right < s.length() && left <= right) {
			//if element not exist in set add and return true
			if (set.add(s.charAt(right))) {
				//move to next element to increase window size
				right++;
				max = Math.max(max, set.size());
			} else {
				//shrink the window size
				set.remove(s.charAt(left));
				left++;
			}

		}
		return max;
	}
}

/**
 * 141. Linked List Cycle
 * <p>
 * Given a linked list, determine if it has a cycle in it.
 * <p>
 * To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the
 * linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.
 * <p>
 * Example 1:
 * <p>
 * Input: head = [3,2,0,-4], pos = 1
 * Output: true
 * Explanation: There is a cycle in the linked list, where tail connects to the second node.
 */
public class LinkedListCycle {
	public boolean hasCycle(ListNode head) {

		ListNode slow = head;
		ListNode fast = head;

		while (fast != null && fast.next != null) {
			slow = slow.next;
			fast = fast.next.next;

			if (slow == fast) {
				return true;
			}
		}

		return false;
	}
}

/**
 * 41. First Missing Positive
 * <p>
 * Given an unsorted integer array, find the smallest missing positive integer.
 * <p>
 * Example 1:
 * <p>
 * Input: [1,2,0]
 * Output: 3
 * Example 2:
 * <p>
 * Input: [3,4,-1,1]
 * Output: 2
 * Example 3:
 * <p>
 * Input: [7,8,9,11,12]
 * Output: 1
 */
public class FirstMissingSmallestPositiveInteger {

	public static void main(String[] args) {
		int[] arr = new int[]{3, 4, -1, 1};

		System.out.println(firstMissingPositive(arr));
	}

	public static int firstMissingPositive(int[] nums) {

		int dummy = nums.length + 2;
		int size = nums.length;

		//for negative and numbers larger than length
		for (int i = 0; i < size; i++) {
			if (nums[i] <= 0 || nums[i] > size) {
				nums[i] = dummy;
			}
		}

		for (int i = 0; i < size; i++) {
			if (nums[i] == dummy || nums[i] == -dummy) {
				continue;
			}
			int val = Math.abs(nums[i]);
			nums[val - 1] = -Math.abs(nums[val - 1]);
		}

		for (int i = 0; i < size; i++) {
			if (nums[i] >= 0)
				return i + 1;
		}

		return size + 1;
	}
}

/**
 * 34. Find First and Last Position of Element in Sorted Array
 * <p>
 * Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value.
 * <p>
 * Your algorithm's runtime complexity must be in the order of O(log n).
 * <p>
 * If the target is not found in the array, return [-1, -1].
 * <p>
 * Example 1:
 * <p>
 * Input: nums = [5,7,7,8,8,10], target = 8
 * Output: [3,4]
 * Example 2:
 * <p>
 * Input: nums = [5,7,7,8,8,10], target = 6
 * Output: [-1,-1]
 */
class FirstAndLastPositionOfElementInSortedArray {
	public int[] searchRange(int[] nums, int target) {
		int start = elementIndex(nums, target, 0, nums.length - 1, true);

		if (start == -1) {
			return new int[]{-1, -1};
		}
		int end = elementIndex(nums, target, 0, nums.length - 1, false);

		return new int[]{start, end};
	}

	public int elementIndex(int[] nums, int target, int low, int high, boolean isSearchForStartIndex) {
		int index = -1;
		while (low <= high) {
			int mid = (low + high) / 2;
			if (nums[mid] == target) {
				index = mid;
				if (isSearchForStartIndex) {
					high = mid - 1;
				} else {
					low = mid + 1;
				}
			} else if (nums[mid] > target) {
				high = mid - 1;
			} else {
				low = mid + 1;
			}
		}
		return index;
	}
}

/**
 * 153. Find Minimum in Rotated Sorted Array
 * <p>
 * Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
 * <p>
 * (i.e.,  [0,1,2,4,5,6,7] might become  [4,5,6,7,0,1,2]).
 * <p>
 * Find the minimum element.
 * <p>
 * You may assume no duplicate exists in the array.
 * <p>
 * Example 1:
 * <p>
 * Input: [3,4,5,1,2]
 * Output: 1
 * Example 2:
 * <p>
 * Input: [4,5,6,7,0,1,2]
 * Output: 0
 */
class FindMinimumInRotatedSortedArray {
	public int findMin(int[] nums) {
		int low = 0;
		int high = nums.length - 1;

		while (low < high) {
			int mid = (low + high) / 2;

			if (nums[mid] > nums[high]) {
				low = mid + 1;
			} else if (nums[mid] < nums[high]) {
				high = mid;
			}
		}
		return nums[low];
	}
}

/**
 * 203. Remove Linked List Elements
 * Remove all elements from a linked list of integers that have value val.
 * <p>
 * Example:
 * <p>
 * Input:  1->2->6->3->4->5->6, val = 6
 * Output: 1->2->3->4->5
 */
public class RemoveLinkedListElements {
	/**
	 * Remove elements iteratively
	 *
	 * @param head
	 * @param val
	 * @return head
	 */
	public ListNode removeElements(ListNode head, int val) {
		if (head == null)
			return head;

		ListNode current = head;
		//check current.next to so we can remove next
		while (current.next != null) {
			if (current.next.val == val) {
				current.next = current.next.next;
			} else {
				current = current.next;
			}

		}

		if (head.val == val)
			head = head.next;

		return head;
	}

	/**
	 * Remove elements recursively
	 *
	 * @param head
	 * @param val
	 * @return head
	 */
	public ListNode removeElementsRecursively(ListNode head, int val) {
		if (head == null) {
			return null;
		}

		ListNode next = removeElementsRecursively(head.next, val);
		if (head.val == val) {
			return next;
		}
		head.next = next;
		return head;
	}
}

/**
 * 83. Remove Duplicates from Sorted List
 * <p>
 * Given a sorted linked list, delete all duplicates such that each element appear only once.
 * <p>
 * Example 1:
 * <p>
 * Input: 1->1->2
 * Output: 1->2
 * Example 2:
 * <p>
 * Input: 1->1->2->3->3
 * Output: 1->2->3
 */
public class RemoveDuplicatesFromSortedList {
	public ListNode deleteDuplicates(ListNode head) {
		//base case
		if (head == null || head.next == null)
			return head;

		ListNode current = head;
		while (current != null) {
			if (current.next == null)
				break;

			if (current.val == current.next.val) {
				//removing duplicate breaking the link
				current.next = current.next.next;
			} else {
				current = current.next;
			}

		}
		return head;
	}
}

/**
 * 11. Container With Most Water
 * <p>
 * Given n non-negative integers a1, a2, ..., an , where each represents a point at coordinate (i, ai). n vertical lines
 * are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis
 * forms a container, such that the container contains the most water.
 * <p>
 * Note: You may not slant the container and n is at least 2.
 * <p>
 * Example:
 * <p>
 * Input: [1,8,6,2,5,4,8,3,7]
 * Output: 49
 * <p>
 * Idea/Proof:
 * <p>
 * The widest container (using first and last line) is a good candidate, because of its width. Its water level is the
 * height of the smaller one of first and last line.
 * All other containers are less wide and thus would need a higher water level in order to hold more water.
 * The smaller one of first and last line doesn't support a higher water level and can thus be safely removed from further
 * consideration.
 */
public class ContainerWithMostWater {
	public int maxArea(int[] height) {

		if (height.length == 0 || height.length == 1) {
			return 0;
		}

		int left = 0;
		int right = height.length - 1;
		int maxWater = 0;

		while (left < right) {
			maxWater = Math.max(maxWater, (right - left) * Math.min(height[left], height[right]));

			//this is for optimization can work with else if condition only
			if (height[right] == height[left]) {
				right--;
				left++;
			} else if (height[left] < height[right]) {
				left++;
			} else {
				right--;
			}
		}
		return maxWater;
	}
}