Problem Given an integer array nums where every element appears three times except for one, which appears exactly once. Find the single element and return it. You must implement a solution with a linear runtime complexity and use only constant extra space. Examples Example 1: Input : nums = [1, 2, 4, 3, 3, 2, 2, 3, 1, 1] Output : 4 ...
Problem Given an array nums of size n, return the majority element. The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array. Definition Majority Element: If an element appears more than n/2 times in array where n is the size of the array. Examples int [] arrA = {1,3,5,5,5,5,4,1,5}; Output: Element appearing more than n/2 times: 5 int []arrA = {1,2,3,4}; Output: No element appearing more than n/2 times ...
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 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 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 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 Given an integer array nums sorted in non-decreasing order, remove the duplicates in-place such that each unique element appears only once. The relative order of the elements should be kept the same. Then return the number of unique elements in nums. Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory. Note that even though we want you to return the new length, make sure to change the original array as well in place. ...
Problem Given the head of a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list. Return the linked list sorted as well. Examples Example 1: Input: head = [1,2,3,3,4,4,5] Output: [1,2,5] ...
Find First Unique Character in a String Problem Given a string s, find the first non-repeating character in it and return its index. If it does not exist, return -1. Examples Example 1: Input: s = "leetcode" Output: 0 Example 2: Input: s = "loveleetcode" Output: 2 ...