code 2 Flashcards
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 1:
Input: nums = [3,2,3]
Output: 3
Example 2:
Input: nums = [2,2,1,1,1,2,2]
Output: 2
public class MajorityElement {
public int majorityElement(int[] nums) {
int majorityElement = nums[0];
int count = 1;
// Iterate through the array starting from the second element
for (int i = 1; i < nums.length; i++) {
// If count becomes 0, reset the majority element to the current element
if (count == 0) {
majorityElement = nums[i];
count = 1;
} else if (nums[i] == majorityElement) {
// If the current element is equal to the majority element, increment count
count++;
} else {
// If the current element is not equal to the majority element, decrement count
count--;
}
}
return majorityElement;
}
public static void main(String[] args) {
MajorityElement me = new MajorityElement();
int[] nums1 = {3, 2, 3}; // Example 1
System.out.println("Majority Element: " + me.majorityElement(nums1));
int[] nums2 = {2, 2, 1, 1, 1, 2, 2}; // Example 2
System.out.println("Majority Element: " + me.majorityElement(nums2));
} }
Contains Duplicate
Given an integer array nums, return true if any value appears at least twice in the array, and return false if every element is distinct.
Example 1:
Input: nums = [1,2,3,1]
Output: true
Example 2:
Input: nums = [1,2,3,4]
Output: false
Example 3:
Input: nums = [1,1,1,3,3,4,3,2,4,2]
Output: true
import java.util.HashSet;
import java.util.Set;
public class ContainsDuplicate {
public boolean containsDuplicate(int[] nums) {
Set<Integer> set = new HashSet<>();</Integer>
// Iterate through the array
for (int num : nums) {
// If the set already contains the current element, return true (duplicate found)
if (set.contains(num)) {
return true;
}
// Otherwise, add the current element to the set
set.add(num);
}
// If the loop completes without finding any duplicates, return false
return false;
}
public static void main(String[] args) {
ContainsDuplicate cd = new ContainsDuplicate();
int[] nums1 = {1, 2, 3, 1}; // Example 1
System.out.println("Contains Duplicate: " + cd.containsDuplicate(nums1));
int[] nums2 = {1, 2, 3, 4}; // Example 2
System.out.println("Contains Duplicate: " + cd.containsDuplicate(nums2));
int[] nums3 = {1, 1, 1, 3, 3, 4, 3, 2, 4, 2}; // Example 3
System.out.println("Contains Duplicate: " + cd.containsDuplicate(nums3));
} }
Meeting rooms
Given an array of meeting time intervals where each interval consists of a start time and an end time, determine if a person could attend all meetings.
Input: intervals = [[0, 30], [5, 10], [15, 20]]
Output: false
import java.util.Arrays;
public class MeetingRooms {
public boolean canAttendMeetings(int[][] intervals) {
// Sort the intervals based on the start time
Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
// Iterate through the sorted intervals
for (int i = 1; i < intervals.length; i++) {
// If the start time of the current interval is less than or equal to the end time of the previous interval,
// then there is a conflict, and the person cannot attend all meetings
if (intervals[i][0] < intervals[i - 1][1]) {
return false;
}
}
// If no conflicts are found, the person can attend all meetings
return true;
}
public static void main(String[] args) {
MeetingRooms mr = new MeetingRooms();
int[][] intervals1 = {{0, 30}, {5, 10}, {15, 20}}; // Example 1
System.out.println("Can Attend All Meetings: " + mr.canAttendMeetings(intervals1));
int[][] intervals2 = {{7, 10}, {2, 4}}; // Example 2
System.out.println("Can Attend All Meetings: " + mr.canAttendMeetings(intervals2));
} }
Move Zeroes
Given an integer array nums, move all 0’s to the end of it while maintaining the relative order of the non-zero elements.
Note that you must do this in-place without making a copy of the array.
Example 1:
Input: nums = [0,1,0,3,12]
Output: [1,3,12,0,0]
Example 2:
Input: nums = [0]
Output: [0]
public class MoveZeroes {
public void moveZeroes(int[] nums) {
// Initialize a variable to keep track of the position to insert non-zero elements
int insertPos = 0;
// Iterate through the array
for (int num : nums) {
// If the current element is non-zero, move it to the insert position
if (num != 0) {
nums[insertPos++] = num;
}
}
// Fill the remaining positions with zeroes
while (insertPos < nums.length) {
nums[insertPos++] = 0;
}
}
public static void main(String[] args) {
MoveZeroes mz = new MoveZeroes();
int[] nums1 = {0, 1, 0, 3, 12}; // Example 1
mz.moveZeroes(nums1);
System.out.println("Output: " + Arrays.toString(nums1));
int[] nums2 = {0}; // Example 2
mz.moveZeroes(nums2);
System.out.println("Output: " + Arrays.toString(nums2));
} }
Squares of a Sorted Array
Given an integer array nums sorted in non-decreasing order, return an array of the squares of each number sorted in non-decreasing order.
Example 1:
Input: nums = [-4,-1,0,3,10]
Output: [0,1,9,16,100]
Explanation: After squaring, the array becomes [16,1,0,9,100].
After sorting, it becomes [0,1,9,16,100].
Example 2:
Input: nums = [-7,-3,2,3,11]
Output: [4,9,9,49,121]
import java.util.Arrays;
public class SortedArraySquares {
public static int[] sortedSquares(int[] nums) {
int[] result = new int[nums.length];
int left = 0;
int right = nums.length - 1;
int index = nums.length - 1;
while (left <= right) {
int leftSquare = nums[left] * nums[left];
int rightSquare = nums[right] * nums[right];
if (leftSquare > rightSquare) {
result[index--] = leftSquare;
left++;
} else {
result[index--] = rightSquare;
right--;
}
}
return result;
}
public static void main(String[] args) {
int[] nums = {-4, -1, 0, 3, 10};
int[] result = sortedSquares(nums);
System.out.println(Arrays.toString(result));
} }
Filling the result array from right to left in the two-pointer approach is efficient because it ensures that the largest squared values, which correspond to the greatest absolute values in the original array, are placed at the end of the result array.
In the given problem, we have a sorted array, and when we square the elements, the larger numbers can appear either at the beginning or at the end, depending on whether they were originally negative or positive. By filling the result array from right to left, we guarantee that the larger squared values are placed in the latter part of the array, which corresponds to the end of the sorted array.
