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
Tag: Leetcode
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 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
Leetcode 41 First Missing Positive Java Solution
Given an unsorted integer array, find the smallest missing positive integer. Example 1: Input: [1,2,0] Output: 3 Example 2: Input: [3,4,-1,1] Output: 2 Example 3: Input: [7,8,9,11,12] Output: 1 Note: Your algorithm should run in O(n) time and uses constant extra space. Solution 1: class Solution { public int firstMissingPositive(int[] nums) { for(int i=0;i<nums.length;i++){ if(nums[i]>0 && nums[i]!=…… Continue reading Leetcode 41 First Missing Positive Java Solution
Leetcode 37 Sudoku Solver Java Solution
Write a program to solve a Sudoku puzzle by filling the empty cells. A sudoku solution must satisfy all of the following rules: Each of the digits 1-9 must occur exactly once in each row.Each of the digits 1-9 must occur exactly once in each column.Each of the the digits 1-9 must occur exactly once in each of the 9 3×3 sub-boxes of the grid. Empty cells are…… Continue reading Leetcode 37 Sudoku Solver Java Solution
Leetcode 36 Valid Sudoku Java Solution
Determine if a 9×9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules: Each row must contain the digits 1-9 without repetition.Each column must contain the digits 1-9 without repetition.Each of the 9 3×3 sub-boxes of the grid must contain the digits 1-9 without repetition. A partially filled sudoku which is valid. The Sudoku board could be partially filled, where empty…… Continue reading Leetcode 36 Valid Sudoku Java Solution