169. Majority Element

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.

Example:

Input: nums = [2,2,1,1,1,2,2]
Output: 2

def majorityElement(nums):
       
    majority = None
    count = 0
   
    for n in nums:
        if majority is None:
            count = 1
            majority = n
        elif n == majority:
            count += 1
        else:
            count -= 1
            if count == 0:
                majority = None
   
   
    return majority




Comments

Post a Comment

Popular posts from this blog

Longest Increasing Subsequence

Problem Given an integer array  nums , return the length of the longest strictly increasing subsequence. Solution DP. Second solution can be O(nlg(n)) First solution : Two for loops checking for each number, what would be the max subsequence based on 1 to n-1. Second solution : Build a sequence, whose i-th position stores the best option (number) for subsequences of length i . Use binary search to make the search log(n) The second approach does not build a single subsequence does produce the correct length. # First: DP, O(N 2 ) from typing import List def lengthOfLIS ( self , nums : List [ int ]) -> int :     local_sol = [ 1 ]*( len ( nums ))     global_sol = 1     for i in range ( 1 , len ( nums )):         for j in range ( i ):             if nums [ i ] > nums [ j ]:                 local_sol [ i ] = max ( local_sol [ i ], local_sol [ j ]+ 1 )...
Read more

K-th smallest in BST

  Problem Given the  root  of a binary search tree, and an integer  k , return  the   k th   smallest value ( 1-indexed ) of all the values of the nodes in the tree . Solution In-order traversal. Recursive or Iterative. Recursive is easy but need to traverse entire tree Or add a lot of ugly code. Iterative is tricky. Two while loops. One always slides to the left. The root is like a pointer.  It does not always come from the stack! # Iterative def kthSmallest ( self , root : Optional [ TreeNode ], k : int ) -> int :         stack = []         while True :             while root :                 stack . append ( root )                 root = root .left             root = stack . pop ()             k -= 1         ...
Read more

Minimum Arrows to Burst Balloons

Image
   Problem Given a set of balloons (start, end), find number of arrows needed to burst. An arrow bursts all the balloons in its vertical path. Solution Greedy. Trick is to sort them by 'end'. Keep a current end that for the current row.  Every time, a balloon starts after the current end Increase the arrow count.  # Greedy def findMinArrowShots ( self , points : List [ List [ int ]]) -> int :                   if not points :             return 0                 points . sort ( key = lambda x : x [ 1 ])             cur_end = points [ 0 ][ 1 ]         arrow = 1                 for start , end in points :             if start > cur_end :                 arrow += 1     ...
Read more