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
Tag: Data Structures
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
Leetcode 35 Search Insert Position Java Position
Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order. You may assume no duplicates in the array. Example 1: Input: [1,3,5,6], 5 Output: 2 Example 2: Input: [1,3,5,6], 2 Output: 1 Example 3:…… Continue reading Leetcode 35 Search Insert Position Java Position
Leetcode 33 Search in Rotated Sorted Array Java Solution
Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand. (i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]). You are given a target value to search. If found in the array return its index, otherwise return -1. You may assume no duplicate exists in the array. Your algorithm’s runtime complexity must be in the order of O(log n).…… Continue reading Leetcode 33 Search in Rotated Sorted Array Java Solution
Leetcode 31 Next Permutation Java Solution
Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers. If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order). The replacement must be in-place and use only constant extra memory. Here are some examples. Inputs are in the left-hand column and its corresponding outputs…… Continue reading Leetcode 31 Next Permutation Java Solution
Leetcode 27 Remove Element Java Solution
Given an array nums and a value val, remove all instances of that value in-place and return the new length. Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory. The order of elements can be changed. It doesn’t matter what you leave beyond the new length. Example 1: Given nums…… Continue reading Leetcode 27 Remove Element Java Solution