Majority Element and Algorithms

These flashcards cover key concepts and algorithms regarding majority elements, skyline problems, maximal leaps, and sum maximization techniques.

What defines a majority element in an array A?

Element x is a majority element if more than half of the elements are x.

How can you determine if there is a majority element in an array?

Sort the array and then count the occurrences of each element. Time complexity is O(n log n).

What is a crucial observation regarding a majority element in subarrays?

If x is a candidate for majority in A, it should appear in a significant number of subarrays.

What is the time complexity of the divide and conquer algorithm for finding a majority element?

The time complexity is O(n log n).

What faster algorithm can find a majority element without divide and conquer?

There is a linear time algorithm with a time complexity of O(n).

What problem does the skyline problem describe?

Given building heights, compute the outline points when viewed from a distance.

What is the task for finding the largest jump in an array A?

Find indices i and j such that A[j] - A[i] is maximal.

What is the first step in the divide and conquer method for finding the largest leap?

Divide the array A[p:r] into two subarrays A[p:q] and A[q+1:r].

What is a key consideration for handling edge cases in finding maximal leaps?

Check combinations of indices across subarrays while keeping track of extremes.

What is T(n) in relation to finding max and min in an array using divide and conquer?

T(n) = 2T(n/2) + O(n), leading to a time complexity of O(n log n).

What does the new version of the algorithm achieve regarding time complexity?

It improves to T(n) = O(n) by using Master Theorem.

What defines the problem of finding indices for maximal sums in array A?

Identify indices such that the sum A[i] + A[i+1] + … + A[j] is maximal.