Objective

Given an array of integers and a value, find a pair of distinct elements in the array that sum to the given value.

Observations

We want to find two elements satisfying:
element1 + element2 = value
We need to find element1 and element2 within the array that satisfy the equation above (if they even exist), but value is known.
We can rearrange this equation as:
- element1 = value - element2
- element2 = value - element1

Code

import java.util.*;

class Solution {
		
	/**
	*	@param int[] nums An array of non-negative integers
	*	@param int sum The value the pair of elements must sum to
	*
	*	@return The distinct pair of VALUES in the array whose corresponding
	*			values sum to the value of 'sum', or [-1, -1] if not found.
	**/
    public static int[] twoSumValues(int[] nums, int sum) {
		// Create a map of num elements to indices
		Map numToIndex = new HashMap();
		
		// Fill the map
		for (int i = 0; i < nums.length; i++) {
			// It doesn't matter if indices are overwritten
			// because the final value will map to the largest index
			numToIndex.put(nums[i], i);
		}
		
		// Iterate through values from smallest index to largest
		// This ensures that overwritten values still match to later indices
		// (e.g., if sum is 4 and there is a 2 at both indices 0 and 1, map only contains 2 mapped to 1)
		for (int i = 0; i < nums.length - 1; i++) {
			
			// See if a match exists in map
			Integer index = numToIndex.get(sum - nums[i]);
			
			// If match exists and the second element's index is later than the first
			if (index != null && index > i) {
				// Return the pair of distinct indices
				return new int[]{nums[i], nums[index]};
			}
		}
		
		// No solution found
		return new int[]{-1, -1};
    }
	
	/**
	*	@param int[] nums An array of non-negative integers
	*	@param int sum The value 
	*
	*	@return The distinct pair of INDICES in the array whose corresponding
	*			values sum to the value of 'sum', or [-1, -1] if not found.
	**/
    public static int[] twoSumIndices(int[] nums, int sum) {
		// Create a map of num elements to indices
		Map numToIndex = new HashMap();
		
		// Fill the map
		for (int i = 0; i < nums.length; i++) {
			// It doesn't matter if indices are overwritten
			// because the final value will map to the largest index
			numToIndex.put(nums[i], i);
		}
		
		// Iterate through values from smallest index to largest
		// This ensures that overwritten values still match to later indices
		// (e.g., if sum is 4 and there is a 2 at both indices 0 and 1, map only contains 2 mapped to 1)
		for (int i = 0; i < nums.length - 1; i++) {
			
			// See if a match exists in map
			Integer index = numToIndex.get(sum - nums[i]);
			
			// If match exists and the second element's index is later than the first
			if (index != null && index > i) {
				// Return the pair of distinct indices
				return new int[]{i, index};
			}
		}
		
		// No solution found
		return new int[]{-1, -1};
    }
}

Objective

Given a string of characters, determine whether or not some permutation of the string creates a palindrome.

Observations

A palindrome is a word that reads the same forward as it does backward.
We can use a sequence of characters to build a palindrome if either of the following conditions are satisfied:
- Each character occurs an even number of times.
- Each character occurs an even number of times except for one character.

Code

import java.util.*;

class Solution {
	/**
	*	@param String s The string to check
	*	@return true if the string can be permuted into a palindrome
	**/
	public static boolean hasPalindromicPermutation(String s) {
		// Create a set to hold unmatched characters
		Set unmatched = new HashSet();
		
		for (int i = 0; i < s.length(); i++) {
			// The current character
			char c = s.charAt(i);
			
			// If the character exists in the set, remove it
			if (unmatched.contains(c)) {
				unmatched.remove(c);
			}
			// Character is unmatched, add it to the set
			else {
				unmatched.add(c);
			}
		}
		
		// For the string to be a palindrome, only 0 or 1 character can be unmatched
		return (unmatched.size() < 2);
	}
}

atebitbyte

Tag Archives: Strings

Find Two Numbers That Sum to a Given Value

Objective

Observations

Permuting a String to Make a Palindrome

Objective

Observations