Problem Given an array of integers occurring between range[0, n) where n is length of the array, write a algorithm to find the element which appears maximum number of times in the array. Examples Example 1: int [] nums = {4, 1, 5, 2, 1, 5, 9, 8, 6, 5, 3, 2, 4, 7}; n = 14 Output: Element repeating maximum no of times: 5, maximum count: 3 ...
Problem Given an array of integers, write a algorithm to find the element which appears maximum number of times in the array. Examples Example 1: int [] arrA = {4, 1, 5, 2, 1, 5, 9, 8, 6, 5, 3, 2, 4, 7}; Output: Element repeating maximum no of times: 5, maximum count: 3 Similar Problem Find the element which appears maximum number of times in the ranged array0, n) ...
Problem Given an array arr[], find the maximum j – i such that arr[j] > arr[i]. Examples Example 1: Input: {34, 8, 10, 3, 2, 80, 30, 33, 1} Output: 6 (j = 7, i = 1) Example 2: Input: {9, 2, 3, 4, 5, 6, 7, 8, 18, 0} Output: 8 ( j = 8, i = 0) ...
Problem Suppose you have an array of 1001 integers. The integers are in random order, but you know each of the integers is between 1 and 1000 (inclusive). In addition, each number appears only once in the array, except for one number, which occurs twice. Assume that you can access each element of the array only once. Describe an algorithm to find the repeated number. If you used auxiliary storage in your algorithm, can you find an algorithm that does not require it? ...
Problem Follow up for Remove duplicates from Sorted Array I: What if duplicates are allowed at most twice? OR Given an integer array nums sorted in non-decreasing order, remove some duplicates in-place such that each unique element appears at most twice. The relative order of the elements should be kept the same. Since it is impossible to change the length of the array in some languages, you must instead have the result be placed in the first part of the array nums. More formally, if there are k elements after removing the duplicates, then the first k elements of nums should hold the final result. It does not matter what you leave beyond the first k elements. ...
Problem Suppose a sorted array 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. Follow up: what if duplicates are allowed? ...
Problem Given an array of integer write an algorithm to find the majority element in it (if exist). Boyer Moore Majority Vote Algorithm We have already seen the problem and some solutions - Majority Element 1 In this article we will see O(n) solution with constant extra space. As per above algorithm we can divide out implementation into two parts First iteration – Find the element which could be a majority element. Second iteration – check the element(found in first iteration) count is greater than n/2 First Iteration – Find the Element Which Could Be a Majority Element Iterate through array and maintain the count of majority_element.(starts with first element in the array.) If next element is same then increment the count If next element is not same then decrement the count. If count becomes zero then majority_element = current element, count =1. After the first iteration majority_element will be the candidate which might have the count > n/2. Second Iteration – Check the Element (found in First iteration) Count is Greater Than n/2 Iterate through array and get the count of element found in first step. If count is >n/2 then print it. If count is less than n/2 then ignore it, array does not have majority element. Complexity ⏰ Time complexity: O(n) 🧺 Space complexity: O(1) Code Java public int majorityElement(int[] arrA) { int size = arrA.length; if (size == 0) return; int majorityElement = arrA[0]; int count = 1; for (int i = 1; i<size; i++) { if (majorityElement == arrA[i]) { count++; } else if (count == 0) { majorityElement = arrA[i]; count = 1; } else { count--; } } //check if majorityElement is appearing more than n/2 times count = 0; for (int i = 0; i<size; i++) { if (arrA[i] == majorityElement) { count++; } } if (count > size / 2) return majorityElement; else return -1; } ...
Problem Given an array of integers, every element appears twice except for one. Find that single one. Examples Example 1: Input: nums = [2,2,1] Output: 1 Example 2: Input: nums = [4,1,2,1,2] Output: 4 Example 3: Input: nums = [1] Output: 1 ...
Problem Given a sorted linked list, delete all duplicates such that each element appear only once. Examples Example 1: Given 1->1->2, return 1->2. Input: head = [1,1,2] Output: [1,2] ...
Problem Write an algorithm to find Whether Given String is palindrome or Not. Definition Palindrome Definition Examples Example 1: Input: str = "malayalam" Output: true Example 2: Input: str = "abc" Output: false Solution Method 1 - Recursion Algorithm If the first and last characters don’t match, return false (not a palindrome). If they match, remove the first and last characters and call the function recursively with the remaining substring. This continues until the entire string is checked. Code Java public Boolean isPalindrome(String s) { if (s.length()<2) { return true; } if (s.charAt(0) == s.charAt(s.length() - 1)) { return isPalindrome(s.substring(1, s.length() - 1)); } else { return false; } } ...