Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one. Example 1: Input: [1,3,4,2,2] Output: 2 Example 2: Input: [3,1,3,4,2] Output: 3 Note: You must not modify the array (assume the array is read…… Continue reading Leetcode Find the Duplicate Number Solution Java Solution

# Category: Leetcode

## Leetcode Unique Binary Search Trees Java Solution

Given n, how many structurally unique BST’s (binary search trees) that store values 1 … n? Example: Input: 3 Output: 5 Explanation: Given n = 3, there are a total of 5 unique BST’s: 1 3 3 2 1 \ / / / \ \ 3 2 1 1 3 2 / / \ \ 2 1 2 3…… Continue reading Leetcode Unique Binary Search Trees Java Solution

## Leetcode Count Complete Tree Nodes Java Solution

Given a complete binary tree, count the number of nodes. Note: Definition of a complete binary tree from Wikipedia:In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2h nodes inclusive at the last level h.…… Continue reading Leetcode Count Complete Tree Nodes Java Solution

## Leetcode Single Number II Java Solution

Given a non-empty array of integers, every element appears three times except for one, which appears exactly once. Find that single one. Note: Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory? Example 1: Input: [2,2,3,2] Output: 3 Example 2: Input: [0,1,0,1,0,1,99] Output: 99 Solution 1: We will use a HashMap and…… Continue reading Leetcode Single Number II Java Solution

## Leetcode Dungeon Game Java Solution

The demons had captured the princess (P) and imprisoned her in the bottom-right corner of a dungeon. The dungeon consists of M x N rooms laid out in a 2D grid. Our valiant knight (K) was initially positioned in the top-left room and must fight his way through the dungeon to rescue the princess. The…… Continue reading Leetcode Dungeon Game Java Solution

## Leetcode 59 Spiral Matrix II Java Solution

Given a positive integer n, generate a square matrix filled with elements from 1 to n2 in spiral order. Example: Input: 3 Output: [ [ 1, 2, 3 ], [ 8, 9, 4 ], [ 7, 6, 5 ] ] Solution 1: class Solution { public int[][] generateMatrix(int num) { int[][] spiralMatrix = new int[num][num]; int m =…… Continue reading Leetcode 59 Spiral Matrix II Java Solution

## Leetcode 54 Spiral Matrix Java Solution

Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order. Example 1: Input: [ [ 1, 2, 3 ], [ 4, 5, 6 ], [ 7, 8, 9 ] ] Output: [1,2,3,6,9,8,7,4,5] Example 2: Input: [ [1, 2, 3, 4], [5, 6, 7, 8], [9,10,11,12] ] Output: [1,2,3,4,8,12,11,10,9,5,6,7] Solution 1: class…… Continue reading Leetcode 54 Spiral Matrix Java Solution

## Leetcode 53 Maximum Subarray Java Solution

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum. Example: Input: [-2,1,-3,4,-1,2,1,-5,4], Output: 6 Explanation: [4,-1,2,1] has the largest sum = 6. Follow up: If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is…… Continue reading Leetcode 53 Maximum Subarray Java Solution

## Leetcode 49 Group Anagrams Java Solution

Given an array of strings, group anagrams together. Example: Input: [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”], Output: [ [“ate”,”eat”,”tea”], [“nat”,”tan”], [“bat”] ] Note: All inputs will be in lowercase.The order of your output does not matter. Solution 1: class Solution { public List<List<String>> groupAnagrams(String[] strs) { Map<String, List<String>> anMap = new HashMap<String, List<String>>(); List<List<String>> retList =…… Continue reading Leetcode 49 Group Anagrams Java Solution

## Leetcode 46 Permutations Java Solution

Given a collection of distinct integers, return all possible permutations. Example: Input: [1,2,3] Output: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ] Solution 1: class Solution { List<List<Integer>> returnList = new ArrayList<>(); int[] used ; public List<List<Integer>> permute(int[] nums) { List<Integer> temp = new ArrayList<Integer>(); used = new int[nums.length]; findPermutations(nums, 0, temp); return returnList; } public void…… Continue reading Leetcode 46 Permutations Java Solution