Scribd
Upload
3 views1 page

Problem Solving 1

The document contains various algorithms and their time and space complexities for solving problems such as 'Two Sum', 'Longest Substring Without Repeating Characters', 'Longest Palindrome Substring', and 'Three Sum'. Each function is implemented in Kotlin, showcasing different approaches like hashing, dynamic programming, and two pointers. The complexities range from O(n) to O(n^2) for time and O(1) to O(n^2) for space, depending on the algorithm used.

Uploaded by

AhmedEl-Menshawi
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
3 views1 page

Problem Solving 1

The document contains various algorithms and their time and space complexities for solving problems such as 'Two Sum', 'Longest Substring Without Repeating Characters', 'Longest Palindrome Substring', and 'Three Sum'. Each function is implemented in Kotlin, showcasing different approaches like hashing, dynamic programming, and two pointers. The complexities range from O(n) to O(n^2) for time and O(1) to O(n^2) for space, depending on the algorithm used.

Uploaded by

AhmedEl-Menshawi
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

// Hash time: O(n) space: O(1) // HashSet + Win time: O(n) space: O(k)

fun twoSum_hash(nums: IntArray, target: Int): IntArray { fun lengthOfLongestSubstring(s: String?): Int {
val n = [Link] if (s == null || [Link] <= 1) return s!!.length
val map: MutableMap<Int, Int> = HashMap() var ans = 0
for (i in 0 until n) { val len = [Link]
if ([Link](target - nums[i])) { val set: MutableSet<Char> = HashSet()
return intArrayOf(map[target - nums[i]]!!,i) var left = 0
} var right = 0
[Link](nums[i], i)} while (right < len) {
return IntArray(0)} while (right < len && ![Link](s[right])) {
Problem10_regularExpressionMatching [Link](s[right])
fun isMatch_api(s: String, p: String): Boolean { right++ }
return [Link]([Link]()) } ans = max([Link](), (right - left).toDouble()).toInt()
[Link](s[left])
left++ } return ans }
// DP time: O(n^2) space: O(n^2) // Two Pointers time: O(n) space: O(1)
fun longestPalindrome_dp(s: String): String { fun maxAreaContainer_tp(height: IntArray): Int {
val len = [Link] val len = [Link]
if (len < 2) { return s } var left = 0
var maxLen = 1 var right = len - 1
var left = 0 var max = (min(
val dp = Array(len) { BooleanArray(len) } height[left].toDouble(),
for (i in 0 until len) { height[right].toDouble()) * (right - left)).toInt()
dp[ i ][ i ] = true } while (left < right) {
for (j in 1 until len) { if (height[left] <= height[right]) {
for (i in 0 until j) { left++
if (s[ i ] == s[ j ]) { } else { right-- }
if (j - i < 3) { max = max( [Link](), (min(
dp[ i ][ j ] = true } else { height[left].toDouble(),
dp[ i ] [ j ] = dp[ i + 1 ][ j - 1] } } height[right].toDouble()
if (dp [ i ][ j ] && j - i + 1 > maxLen) { ) * (right - left)).toDouble() ).toInt() } return max }
maxLen = j - i + 1
left = i }}}
return [Link]( left , left + maxLen ) }
// Hash time: O(n^2) space: O(n) fun searchInsert_bs(nums: IntArray, target: Int): Int {
fun threeSum_hash(nums: IntArray?): List<List<Int>> { val len = [Link]
if (nums == null || [Link] < 3) { return ArrayList()} if (nums[0] > target) { return 0
val ans: MutableSet<List<Int>> = HashSet() } else if (nums[len - 1] < target) { return len}
[Link](nums) var left = 0
val len = [Link] var right = len - 1
for (i in 0 until len - 2) { while (left < right) {
if (nums[i] > 0) { break } val mid = left + (right - left) / 2
if (i > 0 && nums[i] == nums[i - 1]) {continue } if (nums[mid] == target) {
val target = -nums[i] return mid
val set: MutableSet<Int> = HashSet() } else if (nums[mid] < target) {
for (j in i + 1 until len) { left = mid + 1
if ([Link](target - nums[j])) { } else if (nums[mid] > target) { right = mid} }
[Link]([Link](nums[i], nums[j], target - return left
nums[j])) }
} else { [Link](nums[j])}}} return ArrayList(ans) }

You might also like