Kadane’s Algorithm: Max subarray sum in an array
[Question]: Find max sum in an given array
Array-Strings
Array DSA problems in swift.
Find the Majority Element that occurs more than N/2 times
[Question] Find the Majority Element in an given array that occurs more than N/2 times Approach #1 Brute-force Use two loop and compare each elements with rest if it matches increment the counter Approach #2 : Optimal Approach: Moore’s Voting Algorithm Basically, we are trying to keep track of the occurrences of the majority element …
Find the Majority Element that occurs more than N/2 times Read More »
Sort an array of 0s, 1s and 2s || Dutch National Flag solution
[Question]: How to sort an array which has 0s, 1s and 2s Approach #1 Using Dutch National Flag I used three pointers low mid & high The sorting of 0,1,2 is as per below steps arr[0….low-1] contains 0. [most left part] arr[low….mid-1] contains 1arr[high+1….n-1] contains 2. [most right part],So we swap according to the left(0) …
Sort an array of 0s, 1s and 2s || Dutch National Flag solution Read More »
Two Sum Problem
[Question] : Given an array of integers nums and an integer target, find indices of the two numbers which addition equals to target.Example: Input: nums = [2,7,11,15], target = 13 Output: [0,2] Explanation: Because nums[0] + nums[2] == 13, we return [0, 2]. Approach #1 : Using Two pointers: – Step 1: First sort array thenStep 2: If arr[left] …
How to search an element in Sorted Integer matrix ?
Question : Given an m*n 2D sorted matrix of integers, write a program to find if the given integer exists in the matrix.The matrix has the properties below: Approach #1 By removing row and col in each comparisons . Starting from the top right of matrix, move towards the bottom left in search of the …
How to search an element in Sorted Integer matrix ? Read More »
Find missing number from first N natural numbers.
Question: Find the missing number in first n Natural numbers…
How to Find a number which appears once and other numbers are twice ?
[Question]: In a given random array find a number which appears only single time Example : Random array input – [9,2,2,3,4,4,3] output = 9Solution: Step 1: Create a dictionary. Step 2: Create loop and fill the keys with element occurrence.Step 3: Create a loop and return the dictionary element which has only single occurrence .T …
How to Find a number which appears once and other numbers are twice ? Read More »
How to find max consecutive 1’s with Kth allowed zero flip ?
[Question] In a. Given a binary array nums and an integer k, find the maximum number of consecutive 1‘s in the array & you can flip at most k 0‘s.Example: – var arrMix = [1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1] var arrCount = 11 var maxZeros = 2Hence the output will be 8 i.e 1, 1, …
How to find max consecutive 1’s with Kth allowed zero flip ? Read More »
How to find intersection of two sorted array
[Question] In given two sorted arrays find intersection.// Ex–> A: [1 2 3 3 4 5 6] , B: [3 3 5] Output: 3,3,5#Approach: // TC O(n) // SC O(1)
How to find union of two sorted array ?
[Question]: In a given two sorted array find union elements. Output should be sorted. For example : arr1[] = {1,2,3,4,5} arr2[] = {2,3,4,4,5} Output: {1,2,3,4,5}Approach #1: Use Dictionary / Hashset & after it sort the array which SC: O(m+n) TC: O( (m+n)log(m+n) ) Approach #2: Two pointer approach: use two pointer i & j & fill the …