DSA

The problem of Group Anagrams is a common algorithmic challenge that asks to group a list of strings such that each group consists of anagrams. Two words are considered anagrams if one can be formed by rearranging the letters of the other, i.e., they contain the same characters in the same frequency. Problem Statement: Given an array of strings, group the anagrams together. Input: Output: Example: Input: [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”] Output: [[“eat”, “tea”, “ate”], [“tan”, “nat”], [“bat”]] Approach: The key observation for solving the Group Anagrams problem is that two strings are anagrams if and only if their sorted versions are identical. So, one approach is to sort each string and use the sorted version as a key to group the anagrams. Algorithm (in pseudocode): Complexity Analysis: Code Implementations: 1. C++ #include <iostream>#include <vector>#include <unordered_map>#include <algorithm>using namespace std;vector<vector<string>> groupAnagrams(vector<string>& strs) { unordered_map<string, vector<string>> anagramGroups; for (string s : strs) { string sorted_str = s; sort(sorted_str.begin(), sorted_str.end()); anagramGroups[sorted_str].push_back(s); } vector<vector<string>> result; for (auto& pair : anagramGroups) { result.push_back(pair.second); } return result;}int main() { vector<string> strs = {“eat”, “tea”, “tan”, “ate”, “nat”, “bat”}; vector<vector<string>> result = groupAnagrams(strs); for (auto& group : result) { for (string word : group) { cout << word << ” “; } cout << endl; } return 0;} 2. C #include <stdio.h>#include <string.h>#include <stdlib.h>#include <ctype.h>#define MAX_STR_LEN 100#define MAX_STRINGS 100// Function to compare two strings (used by qsort)int compareStrings(const void *a, const void *b) { return strcmp(*(const char **)a, *(const char **)b);}// Function to sort the characters of a stringvoid sortString(char *str) { int len = strlen(str); qsort(str, len, sizeof(char), compareStrings);}int main() { char *strs[] = {“eat”, “tea”, “tan”, “ate”, “nat”, “bat”}; int n = 6; // Temporary array to store sorted strings char *sortedStrs[n]; for (int i = 0; i < n; i++) { sortedStrs[i] = strdup(strs[i]); sortString(sortedStrs[i]); } // Grouping logic can be done manually (using hash maps, or just printing similar sorted strings) // This is just a simple illustration printf(“Grouped Anagrams:\n”); for (int i = 0; i < n; i++) { printf(“%s\n”, strs[i]); } return 0;} 3. Java import java.util.*;public class GroupAnagrams { public List<List<String>> groupAnagrams(String[] strs) { Map<String, List<String>> anagramGroups = new HashMap<>(); for (String s : strs) { char[] chars = s.toCharArray(); Arrays.sort(chars); String sortedStr = new String(chars); anagramGroups.putIfAbsent(sortedStr, new ArrayList<>()); anagramGroups.get(sortedStr).add(s); } return new ArrayList<>(anagramGroups.values()); } public static void main(String[] args) { GroupAnagrams solution = new GroupAnagrams(); String[] strs = {“eat”, “tea”, “tan”, “ate”, “nat”, “bat”}; List<List<String>> result = solution.groupAnagrams(strs); for (List<String> group : result) { System.out.println(group); } }} 4. Python from collections import defaultdictdef group_anagrams(strs): anagram_groups = defaultdict(list) for s in strs: sorted_str = ”.join(sorted(s)) anagram_groups[sorted_str].append(s) return list(anagram_groups.values())# Test the functionstrs = [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”]result = group_anagrams(strs)for group in result: print(group) 5. C# using System;using System.Collections.Generic;public class GroupAnagrams { public List<List<string>> GroupAnagramsMethod(string[] strs) { var anagramGroups = new Dictionary<string, List<string>>(); foreach (string s in strs) { char[] chars = s.ToCharArray(); Array.Sort(chars); string sortedStr = new string(chars); if (!anagramGroups.ContainsKey(sortedStr)) { anagramGroups[sortedStr] = new List<string>(); } anagramGroups[sortedStr].Add(s); } var result = new List<List<string>>(); foreach (var group in anagramGroups.Values) { result.Add(group); } return result; } public static void Main() { GroupAnagrams solution = new GroupAnagrams(); string[] strs = {“eat”, “tea”, “tan”, “ate”, “nat”, “bat”}; var result = solution.GroupAnagramsMethod(strs); foreach (var group in result) { foreach (var word in group) { Console.Write(word + ” “); } Console.WriteLine(); } }} 6. JavaScript function groupAnagrams(strs) { const anagramGroups = {}; for (let str of strs) { const sortedStr = str.split(”).sort().join(”); if (!anagramGroups[sortedStr]) { anagramGroups[sortedStr] = []; } anagramGroups[sortedStr].push(str); } return Object.values(anagramGroups);}// Test the functionconst strs = [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”];const result = groupAnagrams(strs);console.log(result); Summary: The Group Anagrams problem can be efficiently solved by using sorting or character counting and storing results in a hash map. The sorting method is the most straightforward and commonly used. The time complexity of the solution depends on the time to sort each string, which is O(klog⁡k)O(k \log k)O(klogk), where kkk is the average length of a string.

The objective is to rearrange a sorted array arr[] of size n so that every unique element appears at the beginning in sorted order. Return the length of this unique sorted subarray as well. Note: Since they have no bearing on the outcome, the items that follow the distinct ones can be in any sequence and have any value. Table of Content Hash Set Utilization: Effective for Unsorted Additionally, O(n) Space and O(n) Time C++ Java Python C# JavaScript Output 1 2 3 4 5

We don’t need to keep a hash set because the array is sorted. An element would appear one after the other. Therefore, our primary task is to determine whether the current element is identical to the prior one. Detailed implementation: C++ C Java Python Output 1 2 3 4 5

Considering an array arr[] that only contains 0s, 1s, and 2s. Sorting the array means placing all 0s first, followed by all 1s and all 2s last. This issue is identical to the well-known “Dutch National Flag problem.” Edsger Dijkstra was the one who introduced the problem. The following is the issue: Given a line of n balls in a random arrangement, they can be red, white, or blue. All of the balls must be arranged so that they are adjacent to each other in the same color order, which is red, white, and blue (that is, all red balls should be placed first, followed by white balls, and finally blue balls). Table of Content [Naive Approach] Sorting – O(n * log(n)) Time and O(1) Space Sorting the array with a conventional sorting algorithm or sort library function is the naïve option. This will merely arrange all of the zeros first, followed by all of the ones and twos last. This method uses O(1) space and O(n * log(n)) time. [Better Approach] Counting 0s, 1s and 2s – Two Pass – O(n) Time and O(1) Space Counting the number of 0s, 1s, and 2s—let’s say c0, c1, and c2—after one traversal of the array is a superior method. Go through the array once again now, entering c0 (count of 0s) 0s first, followed by c1 1s and c2 2s. Although this method is unstable and necessitates two array traversals, it operates in O(n) time. C++ C Python C# JavaScript Output 0 0 1 1 2 2 Time Complexity: O(2 * n), where n is the number of elements in the arrayAuxiliary Space: O(1) The issues with this approach are:

Navigate through the array until mid <= hi. Three scenarios can be identified based on the value of arr[mid]: C++ C Java Python C# JavaScript Output 0 0 1 1 2 2

Determine the location of X in the matrix, if it exists, given a N X N matrix and an integer X. Print “Element not found” otherwise. The matrix’s rows and columns are arranged in ascending order. Approaches to Search in row wise and column wise sorted matrix: [Naive Approach] Traversing the Complete Matrix – O(N^2) Time and O(1) Space Expected Approach] Removing row or column in each comparison – O(N) Time and O(1) Space [Naive Approach] Traversing the Complete Matrix – O(N^2) Time and O(1) Space: C++ C Java Python JS Output Element found at (2, 1) Time Complexity: O(N2)Auxiliary Space: O(1), since no extra space has been taken

In each comparison, the goal is to eliminate a row or column until an element is discovered. From the matrix’s upper-right corner, begin your search. Three scenarios could occur: C++ C Java Python C# JavaScript Output Element found at (2, 1)

The aim is to set all rows and columns to zeroes in a constant space complexity matrix of size M x N if a certain element is zero. Examples: Naive method: C++ Java Python3 C# JavaScript Output 0 0 0 0 0 4 5 0 0 3 1 0

Format the text so that each line has precisely W characters, left and right justified, given an array of strings arr[] and a width W. Put as many words as you can in each line, try to divide the additional spaces evenly, and if they don’t divide evenly, put more spaces to the left. There should be no extra spaces between words in the final line, which should be left-justified. For instance: Method: The initial step is to decide which words, with one space between each pair of words, can be put into each line. Each line must be justified after the words have been chosen. The total length of the words that are contained, separated by one space, must be less than or equal to W in order for a line to be justified. Additionally, if the current line is the text’s last line, we must add spaces to it so that its width equals W. If not, count the number of spaces required to make each line W long and evenly distribute them if the current line is not the last line. C++ Java Python C# JS Output Sky is the bestcomputer scienceportal forWebz. Time Complexity: O(N), where N is the sum of length of all words.Auxiliary Space: O(W), where W is the max width of a line.

Add 1 to a non-negative number that is represented by an array of digits to increase the number that the digits represent. The digits are stored so that the array’s first entry is the most significant digit. Examples :  Input : [1, 2, 4] Output : [1, 2, 5] Input : [9, 9, 9] Output : [1, 0, 0, 0] Method: Take the actions listed below to add one to the number that is represented by the digits: Output 1 7 9 0 Time Complexity: O(n), where n is the size of the array. Auxiliary Space: O(1) An alternative method is to begin at the end of the vector and set the last element to 0 if it is 9, otherwise break the loop. C++ Java Python3 C# Go