Problem solution in java

Two Number Sum Problem solution in Java

Given an array of integers, return the indices of the two numbers whose sum is equal to a given target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Given nums = [2, 7, 11, 15], target = 9. The output should be [0, 1]. Because nums[0] + nums[1] = 2 + 7 = 9.

Two Number Sum Problem solution in Java

METHOD 1. Naive approach: Use two for loops

The naive approach is to just use two nested for loops and check if the sum of any two elements in the array is equal to the given target.

Time complexity: O(n^2)

import java.util.HashMap; import java.util.Scanner; import java.util.Map; class TwoSum  // Time complexity: O(n^2) private static int[] findTwoSum_BruteForce(int[] nums, int target)  for (int i = 0; i  nums.length; i++)  for (int j = i + 1; j  nums.length; j++)  if (nums[i] + nums[j] == target)  return new int[]  i, j >; > > > return new int[] >; > public static void main(String[] args)  Scanner keyboard = new Scanner(System.in); int n = keyboard.nextInt(); int[] nums = new int[n]; for(int i = 0; i  n; i++)  nums[i] = keyboard.nextInt(); > int target = keyboard.nextInt(); keyboard.close(); int[] indices = findTwoSum_BruteForce(nums, target); if (indices.length == 2)  System.out.println(indices[0] + " " + indices[1]); > else  System.out.println("No solution found!"); > > >

# Output $ javac TwoSum.java $ java TwoSum 4 2 7 11 15 9 0 1

METHOD 2. Use a HashMap (Most efficient)

You can use a HashMap to solve the problem in O(n) time complexity. Here are the steps:

1. Initialize an empty HashMap.
2. Iterate over the elements of the array.
3. For every element in the array —
   • If the element exists in the Map, then check if it’s complement ( target — element ) also exists in the Map or not. If the complement exists then return the indices of the current element and the complement.
   • Otherwise, put the element in the Map, and move to the next iteration.

Time complexity: O(n)

import java.util.HashMap; import java.util.Scanner; import java.util.Map; class TwoSum  // Time complexity: O(n) private static int[] findTwoSum(int[] nums, int target)  MapInteger, Integer> numMap = new HashMap>(); for (int i = 0; i  nums.length; i++)  int complement = target - nums[i]; if (numMap.containsKey(complement))  return new int[]  numMap.get(complement), i >; > else  numMap.put(nums[i], i); > > return new int[] >; > >

METHOD 3. Use Sorting along with the two-pointer approach

There is another approach which works when you need to return the numbers instead of their indexes. Here is how it works:

1. Sort the array.
2. Initialize two variables, one pointing to the beginning of the array ( left ) and another pointing to the end of the array ( right ).
3. Loop until left < right , and for each iteration
   • if arr[left] + arr[right] == target , then return the indices.
   • if arr[left] + arr[right] < target , increment the left index.
   • else, decrement the right index.

This approach is called the two-pointer approach. It is a very common pattern for solving array related problems.

Time complexity: O(n*log(n))

import java.util.Scanner; import java.util.Arrays; class TwoSum  // Time complexity: O(n*log(n)) private static int[] findTwoSum_Sorting(int[] nums, int target)  Arrays.sort(nums); int left = 0; int right = nums.length - 1; while(left  right)  if(nums[left] + nums[right] == target)  return new int[] nums[left], nums[right]>; > else if (nums[left] + nums[right]  target)  left++; > else  right--; > > return new int[] >; > >

Источник

Leetcode Fizz Buzz problem solution

In this Leetcode Fizz Buzz problem solution we have given an integer n, return a string array answer (1-indexed) where:

1. answer[i] == «FizzBuzz» if i is divisible by 3 and 5.
2. answer[i] == «Fizz» if i is divisible by 3.
3. answer[i] == «Buzz» if i is divisible by 5.
4. answer[i] == i if non of the above conditions are true.

Problem solution in Python.

class Solution: def fizzBuzz(self, n: int) -> List[str]: final_list = [] for i in range(1, n+1): if i%15 == 0: final_list.append("FizzBuzz") elif i%5 == 0: final_list.append("Buzz") elif i%3 == 0: final_list.append("Fizz") else: final_list.append(str(i)) return final_list

Problem solution in Java.

class Solution < public ListfizzBuzz(int n) < Listresult = new ArrayList(); for(int i=1;i <=n;i++)< if(i%3==0 && i%5==0)< result.add("FizzBuzz"); continue; >if(i%3==0) < result.add("Fizz"); continue; >if(i%5==0) < result.add("Buzz"); continue; >result.add(i+""); > return result; > >

Problem solution in C++.

class Solution < public: vectorfizzBuzz(int n) < vectorans; for(int i=1;i <=n;i++) < string ap; if(i%3==0) ap+="Fizz"; if(i%5==0) ap+="Buzz"; if(ap.length()==0) ap=to_string(i); ans.push_back(ap); >return ans; > >;

Problem solution in C.

char ** fizzBuzz(int n, int* returnSize) < char **res=(char**)calloc(n,sizeof(char *));int c=0; for(int i=1;i<=n;i++) < if(i%3==0&&i%5==0) < *(res+c)=(char *)calloc(9,sizeof(char)); res[c][0]='F';res[c][1]='i';res[c][2]='z'; res[c][3]='z';res[c][4]='B';res[c][5]='u'; res[c][6]='z';res[c][7]='z';res[c][8]='\0'; c++; >else if(i%3==0) < *(res+c)=(char *)calloc(5,sizeof(char)); res[c][0]='F';res[c][1]='i';res[c][2]='z'; res[c][3]='z';res[c][4]='\0'; c++; >else if(i%5==0) < *(res+c)=(char *)calloc(5,sizeof(char)); res[c][0]='B';res[c][1]='u';res[c][2]='z'; res[c][3]='z';res[c][4]='\0'; c++; >else < int x=0,y=i; while(y) < x++; y=y/10; >*(res+c)=(char *)calloc(x+1,sizeof(char)); res[c][x]='\0'; x--; y=i; while(y) < int m=y%10; res[c][x--]=48+m; y=y/10; >c++; > > *returnSize=c; return res; >

Posted by: YASH PAL

Yash is a Full Stack web developer. he always will to help others. and this approach takes him to write this page.

Источник

Leetcode Word Search II problem solution

In this Leetcode Word Search II problem solution we have Given an m x n board of characters and a list of strings words, return all words on the board.

Each word must be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.

Problem solution in Python.

class Node: def __init__(self, end = 0): self.end = end self.kids = <> class Solution: def findWords(self, board: List[List[str]], words: List[str]) -> List[str]: res, root, m, n = set(), Node(0), len(board), len(board[0]) def setTrie(word): cur = root for w in word: if w not in cur.kids: cur.kids[w] = Node() cur = cur.kids[w] cur.end = 1 return def helper(i, j, root, visited, word): if root.end == 1: res.add(word) visited.add((i, j)) for dx, dy in [[1, 0], [-1, 0], [0, 1], [0, -1]]: x, y = i + dx, j + dy if x < 0 or x >= m or y < 0 or y >= n or (x, y) in visited or board[x][y] not in root.kids: continue helper(x, y, root.kids[board[x][y]], visited, word + board[x][y]) visited.remove((i, j)) return for word in words: setTrie(word) for i in range(m): for j in range(n): if board[i][j] in root.kids: helper(i, j, root.kids[board[i][j]], set(), board[i][j]) return list(res)

Problem solution in Java.

class Solution < public ListfindWords(char[][] board, String[] words) < TrieNode root = new TrieNode(); for (String s : words) root.add(s, 0); Setres = new HashSet<>(); for (int i = 0; i < board.length; i++) < for (int j = 0; j < board[0].length; j++) < find(board, i, j, root.next[board[i][j] - 'a'], res); >> return new ArrayList<>(res); > private void find(char[][] board, int i, int j, TrieNode root, Set res) < if (root == null) return; if (root.word != null) res.add(root.word); char c = board[i][j]; board[i][j] = 'z' + 1; if (i >0) find(board, i - 1, j, root.next[board[i - 1][j] - 'a'], res); if (j > 0) find(board, i, j - 1, root.next[board[i][j - 1] - 'a'], res); if (i < board.length - 1) find(board, i + 1, j, root.next[board[i + 1][j] - 'a'], res); if (j < board[0].length - 1) find(board, i, j + 1, root.next[board[i][j + 1] - 'a'], res); board[i][j] = c; >class TrieNode < TrieNode[] next = new TrieNode[27]; String word; public void add(String s, int index) < char c = s.charAt(index); if (next[c - 'a'] == null) next[c - 'a'] = new TrieNode(); if (index + 1 < s.length()) next[c - 'a'].add(s, index + 1); else next[c - 'a'].word = s; >> >

Problem solution in C++.

class Solution < public: bool dfs(vector> &grid, int i, int j, int index, string &word) < if(i=grid.size() || j>=grid[0].size() || grid[i][j]!=word[index] || grid[i][j]=='*') return false; if(index==word.length()-1) return true; char c=grid[i][j]; grid[i][j]='*'; bool ans=false; if( dfs(grid, i+1 ,j ,index+1 ,word) || dfs(grid, i-1 ,j ,index+1 ,word) || dfs(grid, i ,j+1 ,index+1 ,word) || dfs(grid, i ,j-1 ,index+1 ,word)) ans=true; grid[i][j]=c; return ans; > vector findWords(vector>& grid, vector& word) < vectorans; for(int a=0;a > > if(flag==1) break; > > return ans; > >;

Posted by: YASH PAL

Yash is a Full Stack web developer. he always will to help others. and this approach takes him to write this page.

Источник

HackerRank Lily’s Homework problem solution

In this HackerRank Lily’s Homework problem solution we have given the array arr, determine and return the minimum number of swaps that should be performed in order to make the array beautiful.

Problem solution in Python.

#!/bin/python3 import math import os import random import re import sys # # Complete the 'lilysHomework' function below. # # The function is expected to return an INTEGER. # The function accepts INTEGER_ARRAY arr as parameter. # n = int(input()) l = list(map(int, input().split())) sort = sorted(l) rev = list(reversed(l)) d = <> for i in range(n): if sort[i] not in d: d[sort[i]] = i swaps = 0 i = 0 while i < n: if sort[i] == l[i]: i += 1 continue swaps += 1 l[d[l[i]]], l[i] = l[i], l[d[l[i]]] d[sort[i]] += 1 d = <>for i in range(n): if sort[i] not in d: d[sort[i]] = i swaps_rev = 0 i = 0 while i < n: if sort[i] == rev[i]: i += 1 continue swaps_rev += 1 rev[d[rev[i]]], rev[i] = rev[i], rev[d[rev[i]]] d[sort[i]] += 1 print(min(swaps, swaps_rev))

Problem solution in Java.

import java.io.*; import java.math.*; import java.security.*; import java.text.*; import java.util.*; import java.util.concurrent.*; import java.util.function.*; import java.util.regex.*; import java.util.stream.*; import static java.util.stream.Collectors.joining; import static java.util.stream.Collectors.toList; import java.util.stream.IntStream; public class LilysHomework < private static final Scanner scn = new Scanner(System.in); private static void swap(long[] array, int index1, int index2) < long temp = array[index1]; array[index1] = array[index2]; array[index2] = temp; >private static int swaps(long[] unsortedValues) < int swaps = 0; Maplocations = new HashMap<>(); for (int i = 0; i < unsortedValues.length; i++) < locations.put(unsortedValues[i], i); >long [] sortedValue = unsortedValues.clone(); Arrays.sort(sortedValue); for (int i = 0; i < sortedValue.length; i++) < if (sortedValue[i] != unsortedValues[i]) < swaps++; int swapIndex = locations.get(sortedValue[i]); locations.put(unsortedValues[i], swapIndex); swap(unsortedValues, i, swapIndex); >> return swaps; > public static void main(String[] args) < int numberOfElements = scn.nextInt(); long[] values = new long[numberOfElements]; for (int i = 0; i < numberOfElements; i++) < int value = scn.nextInt(); values[i] = value; >// When all you have is a hammer, everything begins to look like a nail. long [] reverseValue = IntStream.rangeClosed(1, values.length).mapToLong( i -> values[values.length - i]).toArray(); System.out.println(Math.min(swaps(values), swaps(reverseValue))); > >

Problem solution in C++.

#include const int N = int(1e5) + 5; int n, a[N], p[N]; bool used[N]; bool cmp(int i, int j) < return a[i] < a[j]; >int solve() < memset(used, 0, sizeof(used)); int cur = 0; for (int i = 0; i < n; ++i) < int x = i; if (used[x]) continue; while (!used[x]) < used[x] = true; x = p[x]; >cur++; > return n - cur; > int main() < assert(scanf("%d", &n) == 1); for (int i = 0; i < n; ++i) < assert(scanf("%d", &a[i]) == 1); assert(1 std::sort(p, p + n, cmp); for (int i = 0; i + 1

Posted by: YASH PAL

Yash is a Full Stack web developer. he always will to help others. and this approach takes him to write this page.

You may like these posts

Post a Comment

1 Comments

Maybe I am missing something but I think this is not quite correct..

long [] reverseValue = IntStream.rangeClosed(1, values.length).mapToLong(
i -> values[values.length - i]).toArray();
System.out.println(Math.min(swaps(values), swaps(reverseValue)));

providing "values" and "reverseValue" arrays as parameters to "swaps" method is the same thing.. both of them are sorted to the same array in the "swaps" method.. I think the idea was to do a reverse sort (descending) INSIDE the "swaps" method.. Reply Delete

Источник

Leetcode Group Anagrams problem solution

In this Leetcode Group Anagrams problem solution, we have given an array of strings strs, group the anagrams together. You can return the answer in any order. An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Problem solution in Python.

class Solution: def groupAnagrams(self, strs: List[str]) -> List[List[str]]: anagrams = <> for s in strs: s_sorted = "".join(sorted(s)) if s_sorted not in anagrams: anagrams[s_sorted] = [] anagrams[s_sorted].append(s) return [list(value) for key, value in anagrams.items()]

Problem solution in Java.

class Solution < public List> groupAnagrams(String[] strs) < List> result = new ArrayList>(); Map> groups = new HashMap>(); for (int i = 0; i < strs.length; i++)< String str = strs[i]; String key = buildAnagramsKey(str); if (!groups.containsKey(key))< groups.put(key, new ArrayList()); > groups.get(key).add(str); > for (Map.Entry> pair : groups.entrySet()) < result.add(pair.getValue()); >return result; > public String buildAnagramsKey(String str) < int[] map = new int[26]; for (Character c : str.toCharArray())< map[c - 'a'] += 1; >StringBuilder build = new StringBuilder(); for (int i = 0; i < 26; i++)< build.append(map[i]); build.append((char) (i + 'a')); >return build.toString(); > >

Problem solution in C++.

class Solution < public: vector> groupAnagrams(vector& strs) < unordered_map m; vector> ans; for(int i=0;i for(auto it= m.begin();it!=m.end();it++)< ans.push_back(it->second); > return ans; > >;

Problem solution in C.

struct Node< int key; char *data; struct Node *next; >; int checkAnagram(char *str[],int length) < int i=0; size_t size; int sumAllChar=0; struct Node *newNode; struct Node *array=(struct node*)(malloc(length*sizeof(struct Node))); for(i=0;ifor(i=0;i else< newNode = createNewNode(sumAllChar,str[i]); struct Node *temp = existsNode; while(temp && temp->next!=NULL)< temp = temp->next; > temp->next=newNode; > > for(i=0;idata); temp = temp->next; > > > > struct Node *checkKeyExists(struct Node *array,int key,int length) < int i=0; for(i=0;i> return NULL; > struct Node* createNewNode(int number,char *data)< struct Node *newNode = (struct Node *)malloc(sizeof(struct Node)); newNode->key = number; newNode->data=data; newNode->next = NULL; return newNode; > int sumOfAllCharacters(char *str) < int i=0; int sumAllChar = 0; int len = strlen(str); for(i=0;ireturn sumAllChar; >

Posted by: YASH PAL

Yash is a Full Stack web developer. he always will to help others. and this approach takes him to write this page.

Источник